JDk1.8HashMap的源码分析

系统管理员 2023-07-13 03:34 4阅读 0赞

# JDk1.8HashMap的源码分析 #

#### HashMap用数组存放数据（总结） ####

1.  调用键的hashCode()获得键的哈希值
2.  用哈希值，计算一个下标值 i
3.  新建Entry对象来封装键和值
4.  Entry对象放在 i 位置

1.  空位置，直接放入
2.  有数据，依次用equals()比较是否相等
3.  找到相等的，覆盖值
4.  没有相等的，链表连接在一起
5.  负载率、加载因子到0.75
6.  新建翻倍容量的新数组
7.  所有数据，重新哈希，放入新数组
8.  jdk1.8
9.  链表长度到8，转成红黑树
10. 红黑树数据量减少到6，转回成链表

#### hashCode() ####

Object的方法  
Object中默认实现是使用内存地址，作为哈希值  
如果对象作为键，放入HashMap，应该重写hashCode()，使用属性数据，来计算哈希值

#### HashMap中根据hash值求得index的 ####

// 先用key求得hash值
            static final int hash (Object key){ 
                // h = key.hashCode() 为第一步 取hashCode值
                // h ^ (h >>> 16) 为第二步 高位参与运算
                int h;
                return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            }

#### JDK1.8HashMap的put方法源码如下 ####

/** * (1).判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容； * (2).根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向(6)，如果table[i]不为空， 转向(3)； * (3).判断 table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向(4)，这里的相同指的是hashCode以及equals； * (4).判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向(5)； * (5).遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作， * 否则进行链表的插入操作； 遍历过程中若发现key已经存在直接覆盖value即可； * (6).插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容 */
            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;
                // 步骤(1)：tab为空则创建
                if ((tab = table) == null || (n = tab.length) == 0) { 
                    n = (tab = resize()).length;
                }
                // 步骤(2)：计算index，并对null做处理
                if ((p = tab[i = (n - 1) & hash]) == null) { 
                    tab[i] = newNode(hash, key, value, null);
                } else { 
                    Node<K, V> e;
                    K k;
                    // 步骤(3)：节点key存在，直接覆盖value
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k)))) { 
                        e = p;
                        // 步骤(4)：判断该链为红黑树
                    } else if (p instanceof HashMap.TreeNode) { 
                        e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
                        // 步骤(5)：该链为链表
                    } else { 
                        for (int binCount = 0; ; ++binCount) { 
                            if ((e = p.next) == null) { 
                                p.next = newNode(hash, key, value, null);
                                //链表长度大于8转换为红黑树进行处理
                                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                { 
                                    treeifyBin(tab, hash);
                                }
                                break;
                            }
                            // key已经存在直接覆盖value
                            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;
                // 步骤(6)：超过最大容量 就扩容
                if (++size > threshold) { 
                    resize();
                }
                afterNodeInsertion(evict);
                return null;
            }

[美团的Java 8系列之重新认识HashMap][Java 8_HashMap]  
参考：https://tech.meituan.com/2016/06/24/java-hashmap.html

[Java 8_HashMap]: https://tech.meituan.com/2016/06/24/java-hashmap.html