HashMap知识小结

一、常用方法

map.put(); //向集合中插入键值对 map.get(); //根据key获取value map.size(); //获取集合存储键值对个数 map.clear(); //清除集合中所有键值对 map.isEmpty(); //判断集合中是否为null，返回布尔值 map.remove(); //根据key删除键值对并返回value值 map.containsKey(); //判断键值对中是否存在给定的key值的键值对 map.containsValue(); //判断键值对中是否存在给定的value值的键值对 map.entrySet(); //返回所有的键值对 map.replace(); //根据传入的key将传入的value替换

二、结构

HashMap在jdk8之前采用数组+链表的数据结构，在jdk8时采用数组+链表+红黑树的数据结构。

3、源码显示

hashmap的初始容量是16； 最大容量是2的三十次方 每个键值对传入进来后都会转化成node存储，其中包含key、value，next、hash。 负载因子是0.75，当键值对个数达到当前容量的75%时，进行扩容，容量*2。

---

重点来了，扩容过程如下：

首先创建一个容量为原来2倍的数组，将原来数组的数据拷贝过去，那么拷贝的过程是怎么样的呢？这个过程分为三种情况：

1.如果node的next为null，则重新计算在新的数组中的位置，也就是它本来后面就没有链表/红黑树。 2.如果是红黑树，就用split方法处理，原理是将红黑树拆分成两个TreeNode链表，判断每个链表是否小于等于6，如果是则转换成链表插入到新的数组中，否则成为一个新的红黑树插入数组。 3.如果是链表则直接插入新的数组中，确保顺序不变。

//扩容源码： final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

---

四、put()和get()实现细节

put键值对的方法的过程是：

①判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容； ②根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③； ③判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals； ④判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤； ⑤遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可； ⑥插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

get值方法的过程是:

1、指定key 通过hash函数得到key的hash值 int hash=key.hashCode();

2、调用内部方法 getNode()，得到桶号(一般都为hash值对桶数求模) int index =hash%Entry[].length;

3、比较桶的内部元素是否与key相等，若都不相等，则没有找到。相等，则取出相等记录的value。

4、如果得到 key 所在的桶的头结点恰好是红黑树节点，就调用红黑树节点的 getTreeNode() 方法，否则就遍历链表节点。getTreeNode 方法使通过调用树形节点的 find()方法进行查找。由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率很高。

5、如果对比节点的哈希值和要查找的哈希值相等，就会判断 key 是否相等，相等就直接返回；不相等就从子树中递归查找。

HashMap中直接地址用hash函数生成；解决冲突，用比较函数解决。如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候)。

标题四内容取自：HashMap原理的深入理解