第1章-002节
一、put()⽅法和get()⽅法
1.1 put()⽅法
put函数⼤致的思路为：
- 对key的hashCode()做hash，然后再计算index;
- 如果没碰撞直接放到bucket⾥；
- 如果碰撞了，以链表的形式存在buckets后；
- 如果碰撞导致链表过⻓(⼤于等于TREEIFY_THRESHOLD)，就把链表转换成红⿊树；
- 如果节点已经存在就替换old value(保证key的唯⼀性)
- 如果bucket满了(超过load factor*current capacity)，就要resize。
具体代码的实现如下：
public V put(K key, V value) {// 对key的hashCode()做hash return putVal(hash(key), key, value, false, true);}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //如果当前map中⽆数据，执⾏resize⽅法。并且返回n if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; ///如果要插⼊的键值对要存放的这个位置刚好没有元素，那么把他封装成Node对象，放在这个位置上就完事了if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //否则的话，说明这上⾯有元素 else { Node<K,V> e; K k; //如果这个元素的key与要插⼊的⼀样，那么就替换⼀下，也完事。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //1.如果当前节点是TreeNode类型的数据，执⾏putTreeVal⽅法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //还是遍历这条链⼦上的数据，跟jdk7没什么区别 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //2.完成了操作后多做了⼀件事情，判断，并且可能执⾏treeifyBin⽅法，treeifyBin()就是将链表转换成红⿊树。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 写⼊ if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //判断阈值，决定是否扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }⼀直到JDK7为⽌，HashMap的结构基于⼀个数组以及多个链表的实现，hash值冲突的时候，就
将对应节点以链表的形式存储。
这样⼦的HashMap性能上就抱有⼀定疑问，如果说成百上千个节点在hash时发⽣碰撞，存储⼀
个链表中，那么如果要查找其中⼀个节点，那就不可避免的花费O(N)的查找时间，这将是多么⼤
的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下，链表查找的时间复杂度为
O(n),⽽红⿊树⼀直是O(logn),这样会提⾼HashMap的效率。JDK7中HashMap采⽤的是位桶+链表
的⽅式，即我们常说的散列链表的⽅式，⽽JDK8中采⽤的是位桶+链表/红⿊树（有关红⿊树请
查看红⿊树）的⽅式，也是⾮线程安全的。当某个位桶的链表的⻓度达到某个阀值的时候，这个
链表就将转换成红⿊树。
JDK8中，当同⼀个hash值的节点数不⼩于8时，将不再以单链表的形式存储了，会被调整成⼀颗
红⿊树。这就是JDK7与JDK8中HashMap实现的最⼤区别。JDK中Entry的名字变成了Node，原
因是和红⿊树的实现TreeNode相关联。
transient Node<K,V>[] table;
当冲突节点数不⼩于8-1时，转换成红⿊树。
static final int TREEIFY_THRESHOLD = 8;
总结下put的过程：
当程序试图将⼀个key-value对放⼊HashMap中时，程序⾸先根据该 key 的 hashCode() 返回值
决定该 Entry 的存储位置， 该位置就是此对象准备往数组中存放的位置。
如果该位置没有对象存在，就将此对象直接放进数组当中；如果该位置已经有对象存在了，则顺
着此存在的对象的链开始寻找(为了判断是否是否值相同，map不允许键值对重复)， 使⽤ equals
⽅法进⾏⽐较，如果对此链上的 key 通过 equals ⽐较有⼀个返回 true，新添加 Entry 的 value
将覆盖集合中原有 Entry 的 value，但key不会覆盖；如果对此链上的每个对象的 equals ⽅法⽐
较都为 false，则将该对象放到数组当中，然后将数组中该位置以前存在的那个对象链接到此对
象的后⾯，即新值存放在数组中，旧值在新值的链表上。
1.2 get()⽅法
在理解了put之后，get就很简单了。⼤致思路如下：
- bucket⾥的第⼀个节点，直接命中；
- 如果有冲突，则通过key.equals(k)去查找对应的entry
若为树，则在树中通过key.equals(k)查找，O(logn)；
若为链表，则在链表中通过key.equals(k)查找，O(n)。
具体代码的实现如下：
public V get(Object key) {Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;}
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 直接命中 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 未命中 if ((e = first.next) != null) { // 在树中get if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 在链表中get do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
1.3 null key存取
- 对于put⽅法来说，HashMap会对null值key进⾏特殊处理，总是放到table[0]位置
- 对于get⽅法来说，同样当key为null时会进⾏特殊处理，在table[0]的链表上查找key为null的元素
private V putForNullKey(V value) {for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; }大家一起学习丫~
java集合学习 文章被收录于专栏
主要讲解java集合相关的概念、原理和部分面试题。 共计11章。 不断更新中。。。 （摘自某大佬）
中移(苏州)软件技术有限公司工作强度 29人发布
