HashMap总结

hashmap的基于数组和链表及红黑树实现的哈希表。采用数组作为键值对的容器，数组中存放的是单链表的头节点。hashmap采用链表的方式(链地址法)处理hash冲突，当发生冲突时，将冲突的元素链接到链表上去。hashmap的key和value都支持null值，而hashtable则不支持。它不是同步的，但是可以通过适当的方法变为支持同步的。

哈希表

1、 散列表，是根据关键码值（Key）进行访问的数据结构，也就是说，通过将Key映射到表中一个位置来获取记录，加快查找的速度，这个映射函数叫做撒案列函数，存放记录的结构 称之为散列表 寻址容易，删除插入也容易的数据结构 张三 15376467384 ZS 90+83 = 173 //key value 李四 18548787753 LS 76+83 = 159 王五 19847875837 WW 87+87 = 174 张帅 14338477838 ZS 90+83 = 173 class People{ private String name; private String number; } 2、 查找的时间复杂度： 链表 O(N) 二叉排序树 O(log2 N) 散列表 key - value O(1) key -》 hash函数 -》 name所对应的首字母的ASCII值 -> 散列码 3、哈表冲突 通常以下几种方式构造哈希函数 1）直接定址法 key address(key) = a*key + b 2）平方取中法 key 108 109 110 = 108^2 109^2 110^2 3）折叠法 key -》 拆分为几部分 区域号-书架号-图书编号 4）除留取余法 key -》 hash表的最大长度m 取不大于m的质数 key%质数 4、解决冲突 1）开放地址法 12 13 25 23 hash表的长度14 hash函数key%13 2）链地址法

HashMap基本用法

static void main(String[] args) { //声明HashMap对象 Map<String, Integer> map = new HashMap<>(); //添加元素 map.put("zhangsan", 98); map.put("lisi", 100); map.put("wangwu", 102); map.put("zhangsan", 1000); //根据key获取记录 System.out.println(map.get("lisi")); //100 //根据key删除记录 System.out.println(map.remove("lisi"));//100 //获取map中记录个数 System.out.println(map.size()); //2 //判断map集合中是否包含键为key的记录 System.out.println(map.containsKey("zhangsan"));//true System.out.println(map.containsKey("xiaohua"));//false System.out.println(map.isEmpty());//false //清空map集合 map.clear(); System.out.println(map.isEmpty());//true }

HashMap迭代器的使用：

public static void main(String[] args) { HashMap<String, String> map = new HashMap<>(); map.put("a", "tulun1"); map.put("b", "tulun2"); map.put("c", "tulun3"); map.put("aa", "tulun4"); Iterator<Map.Entry<String, String>> itr = map.entrySet().iterator(); while(itr.hasNext()){ Map.Entry<String, String> entry = itr.next(); System.out.println(entry.getKey() + ":: "+entry.getValue()); } }

迭代后的结果

自定义HashMap

/** * 自定义HashMap，hash算法直接使用HashMap中的hash算法，解决哈希冲突 * 采用链地址法，即链表+数组实现，包括方法有put(K key, V value),get(K key), remove(K key)等方法 * * hashCode方法是将引用类型的内存地址转换为一个32位的整型返回，所以存在一定的 * 限制，导致两个不同对象有可能hashCode也会相等，这样的话比较了hash值还需要比较 引用，才能够保证两个对象完全相等。 * * 哈希表扩容 * * HashMap迭代器实现 * * 1）哈希表中数据分布是不连续的，在迭代器初始化的过程中必须先跳转到第一个非空数据节点 * 2）当迭代器的下标到达当前桶的链表末尾时，迭代器下标跳转到下一个非空桶的第一个数据节点 * */ class MyHashMap<K,V>{ private Node<K, V>[] table; private int size; class Node<K,V>{ protected K key; protected V value; protected int hash; protected Node<K, V> next; public Node(K key, V value, int hash) { this.key = key; this.value = value; this.hash = hash; } } public MyHashMap(int capacity){ table = new Node[capacity]; } public Iterator<Node<K, V>> iterator(){ return new Itr(); } class Itr implements Iterator<Node<K, V>>{ private int currentIndex;//当前桶的位置 private Node<K, V> nextNode;//返回的下一个数据节点 private Node<K, V> currentNode; //上一次next返回的数据节点 public Itr(){ if(MyHashMap.this.isEmpty()){ return; } for(int i=0; i < table.length; i++){ currentIndex = i; Node<K, V> firstNode = table[i]; if(firstNode != null){ nextNode = firstNode; return; } } } @Override public boolean hasNext() { return nextNode != null; } @Override public Node<K, V> next() { //返回下一个数据节点 currentNode = nextNode; //nextNode指向自己的next nextNode = nextNode.next; if(nextNode == null){ //说明当前桶的链表已经遍历完毕 //寻找下一个非空的桶 for(int i=currentIndex+1; i<MyHashMap.this.table.length; i++){ //设置当前桶位置 currentIndex = i; Node<K,V> firstNode = MyHashMap.this.table[currentIndex]; if(firstNode != null){ nextNode = firstNode; break; } } //nextNode保存的就是下一个非空的数据节点 } return currentNode; } @Override public void remove() { if(currentNode == null){ return; } K currentKey = currentNode.key; MyHashMap.this.remove(currentKey); currentNode = null; } } public void resize(){ //扩容桶table Node<K, V>[] newTable = new Node[table.length * 2]; for(int i=0; i<table.length; i++){ //将oldTable中每一个位置映射到newTable中 rehash(i, newTable); } this.table = newTable; } public void rehash(int index, Node<K,V>[] newTable){ Node<K, V> currentNode = table[index]; if(currentNode == null){ return; } Node<K, V> lowListHead = null; //低位的头 Node<K, V> lowListTail = null; //低位的尾 Node<K, V> highListHead = null; //高位的头 Node<K, V> highListTail = null; //高位的尾 //currentNode表示oleTable下index位置中当前节点 while(currentNode != null){ //当前节点在newTable中的位置 int newIndex = newTable.length-1 & hash(currentNode.key); if(newIndex == index){ //映射到原先下标处 if(lowListHead == null){ lowListHead = currentNode; lowListTail = currentNode; }else{ lowListTail.next = currentNode; lowListTail = lowListTail.next; } }else{ //newIndex与index不等，映射到高位下标处 if(highListHead == null){ highListHead = currentNode; highListTail = currentNode; }else{ highListTail.next = currentNode; highListTail = lowListTail.next; } } currentNode = currentNode.next; } //将lowList head->tail之前的节点链接到index位置 if(lowListTail != null){ newTable[index] = lowListHead; lowListHead.next = null; } //将highList head->tail之前的节点链接到index+table.length位置 if(highListTail != null){ newTable[index+this.table.length] = highListHead; highListHead.next = null; } } public int hash(Object key) { int h; return (h = key.hashCode()) ^ (h >>> 16); } public void put(K key, V value){ //确定所要添加元素的位置 int hash = hash(key);//散列码 int index = table.length-1 & hash;//确定的位置 //newNode -》table[index] == null || key在map不存在 //table[index]已经存在数据 //table[index]不存在数据 Node<K, V> firstNode = table[index];//得到该位置的第一个节点 if(firstNode == null){ table[index] = new Node(key, value, hash); size++; }else{ //第一种情况 key已经存在 考虑新值覆盖旧值 //第二种情况 key不存在 封装一个新的node尾插法插入链表 if(firstNode.key.equals(key)){ firstNode.value = value; //新值替换旧值 }else{ Node<K,V> tmp = firstNode; while(tmp.next != null && !tmp.key.equals(key)){ tmp = tmp.next; } if(tmp.next == null){ if(tmp.key.equals(key)){ tmp.value = value; //新值替换旧值 }else{ tmp.next = new Node(key, value, hash); size++; } }else{ tmp.value = value; } } } } public boolean remove(K key){ int hash = hash(key); int index = table.length-1 & hash; Node<K, V> firstNode = table[index]; if(firstNode == null){ return false; }else{ if(firstNode.next == null){ if(firstNode.key.equals(key) && firstNode.hash == hash){ //为什么判断key是否相等的同时还需要判断散列码 table[index] = null; return true; } } Node<K,V> tmpPrev = firstNode; Node<K, V> tmp = firstNode.next; while(tmp.next != null){ if(tmp.key.equals(key) && tmp.hash == hash){ //tmp之前节点的next指向tmp.next tmpPrev.next = tmp.next; size--; }else{ tmpPrev = tmp; tmp = tmp.next; } } } return false; } public Node<K,V> get(K key){ //获取对应key所在数组的index int hash = hash(key);//散列码 int index = table.length - 1 & hash; //定位key记录所在的位置 Node<K, V> firstNode = table[index]; if (firstNode == null) { return null; } if (hash == firstNode.hash && key == firstNode.key) { return firstNode; } else { //遍历链表 Node<K, V> currentNode = firstNode.next; while (currentNode != null) { if (currentNode.hash == hash && currentNode.key == key) { return currentNode; } currentNode = currentNode.next; } } return null; } public boolean isEmpty(){ return size == 0; } }

HashMap源代码分析

继承的类与实现的接口

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

继承了AbstractMap类； 实现了Map<K,V>, Cloneable, Serializable三个接口。

类的属性

初始化容量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

初始化容量为1左移4位（即二进制00001左移4位变为10000=16）

最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

最大容量为2^30

桶中结构转化为红黑树对用的table的最小大小

static final int MIN_TREEIFY_CAPACITY = 64;

默认加载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f

由链表转换为树的阈值

static final int TREEIFY_THRESHOLD = 8;

桶上的节点个数大于8时会转为红黑树

由树转换为链表的阈值

static final int UNTREEIFY_THRESHOLD = 6;

桶上的绩点个数小于6时会转为链表

存储元素的数组

transient Node<K,V>[] table;

大小总是2的幂次方

哈希表中节点的集合

transient Set<Map.Entry<K,V>> entrySet;

类的构造函数

HashMap有4种构造方法：

1、指定初始化容量和加载因子

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }

2、指定初始容量

public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }

3、使用默认值

public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

4、从其他Map实例创建HashMap对象

public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

常用的方法

put操作

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0)//tab为空 n = (tab = resize()).length;//重置大小 if ((p = tab[i = (n - 1) & hash]) == null)//首节点为null tab[i] = newNode(hash, key, value, null);//插入节点 else {//首节点不为null Node<K,V> e; K k; if (p.hash == hash &&//这里p即为首节点 ((k = p.key) == key || (key != null && key.equals(k))))//是首节点 e = p;//e指向首节点 else if (p instanceof TreeNode)//p不是首节点，如果p是TreedNode的实例，也就是按照树结构存放的话 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//按照树的方式put节点 else {//如果p不是首节点，且是按照链表存放 for (int binCount = 0; ; ++binCount) {//遍历链表 if ((e = p.next) == null) {//判断p.net是否为null，是则到了链表尾 p.next = newNode(hash, key, value, null);//插到尾部 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //节点数量大于阈值TREEIFY_THRESHOLD treeifyBin(tab, hash);//将链表存储转化为树存储 break;//结束循环 } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//如果key存在 break;//结束循环 p = e;//上边以及赋值e=p.next，这里就相当于p=p.next，移动指针到下一个节点 } } if (e != null) { // existing mapping for key //如果key存在 V oldValue = e.value;//得到旧value if (!onlyIfAbsent || oldValue == null)//如果不是仅当键不存在才插入或者原来的值为null e.value = value;//赋值value给e afterNodeAccess(e);//添加之后的操作 return oldValue;//返回旧值 } } ++modCount;//操作次数加1 if (++size > threshold)//判断阈值 resize();//更改大小 afterNodeInsertion(evict); return null; }

大致的流程图： 大致思路流程： 首先判断hashtable是否为null，如果为null,则先初始化容量；根据key计算处于桶中的索引位置，然后判断头节点是否为null，如果为null则插入节点；如果头节点不为空，判断key是否存在，如果是新值覆盖旧值，如果不存在，先判断是按照链表存储还是按照树的结构存储，如果是按照树的结构存储则就按照树的插入节点的方法插入，否则按照链表的方式插入。在按链表的方式插入时，移动引用，找到链尾，插入节点。在移动过程中会判断当前链表的容量与初始阈值的大小（判断链表长度是否大于8，如果大于8，则传化为红黑树；检查key是否存在，key不存在插入新节点，存在新值覆盖旧值），以此来决定要不要转化为树形结构存储。最后，插入成功返回旧的值，插入失败返回null。 参数： hash : key的hash值 key : 键 value : 值 onlyIfAbsent : 仅当键不存在才添加 evict : 是否回收

判断key是否存在

public boolean containsKey(Object key) { return getNode(hash(key), key) != null; }

resize();get();remove()方法的分析差不多一样这里就不分析了

HashMap和Hashtable对比