HashMap详解

讲解步骤基础知识工作原理关键代码核心方法基础知识

数组结构

数组接口,在查询数据方面,具备优势

链表结构

链表结构,在增删数据方面,具备优势

红黑树结构

红黑树结构,在查询数据方面,数据量较大的时候,具备一定的优势

什么是散列(哈希)表

散列表,顾名思义,就是将数据分布在不同的列 但是散列表并不是完全将数据分散在不同的列,而是按照某种规则,将具备同样规则的数据存储在同一列。 即具备相同规则的数据存储在同一列,规则不同的数据分布在不同的列。 这种规则最终的产生与哈希值有关。 这里需要注意的事,哈希值只是确定最后存储列的因素,也就是说不同的哈希值可能会存在同一列。

什么是哈希值

哈希值简单的说,就是hashCode方法产生的值。 默认的hashCode方法是由其地址值最终产生一个哈希值。 由于HashMap中的元素是否存储是由键来决定,所以如果自定义的类需要存储在键,且想遵循自己的存储规则,需要重写HashCode方法 又因为Map集合的键是不能重复的,所以需要重写equals方法,定义去重规则。工作原理存储结构

HashMap基于散列法,又称哈希法：数组+链表+红黑树。

HashMap需要同时存储一对键和值。 Map集合中提供了put(key, value)方法,所有的键和值会被封装到一个Entry实现类(Node)对象,存储到集合中。 在存储的过程中,会先通过hashCode()方法获取一个哈希值,并通过这个哈希值,与数组的长度进行一定的运算,得到一个索引值(存储的列) 在通过equals方法来判断这个元素是否已存在,不存在则存储在该列,若存储,则保留原来的数据。 存储在一列的数据,将以链表的形式,前后关联,这样有利于将来进行删除的时候提高效率。 但是如果一列的桶结构数据过多,就会导致查询的效率降低。 为了优化桶结构带来的问题,HashMap中会去检查,当一列的桶结构数据达到8个以上,就降这一列树化(转变为树结构)名词理解所有的数据都是以Node节点为单位。 hash值:哈希值,该方法内部提供了一个扰动函数——int hashCode() 扰动函数:用于产生哈希值,前16位与后16位做异或运算,提高低位随机性。——h = key.hashCode()) ^ (h >>> 16) 路由寻址:由数组长度与哈希值产进行与操作,产生最终的存储列(索引位置):(table.length-1)&node.hash Hash碰撞：哈希值如果相同，就会存储到相同的列。 链化：哈希值相同，就会存储在同系列，产生桶状结构，桶结构过长，查询数据低效。 红黑树：jdk8引入,类似于二叉树,可以避免过长的桶状结构扩容原理扩容:增加数组长度。目的在于解决数据过多，链化严重，默认以两倍的长度扩容。 ①一列添加第8+个元素，且数组长度小于64，会优先扩容。 ②一列添加第8+个元素，且数组长度达到64个，会优先树化。 ③添加元素后,若哈希表中元素总个数超过阈值(一个指定的值)，会进行扩容。 ④扩容后，会重新根据数组长度和哈希值计算存储位置。关键代码核心字段static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 默认数组大小 static final int MAXIMUM_CAPACITY = 1 << 30; 数组最大长度 static final float DEFAULT_LOAD_FACTOR = 0.75f; 默认负载因子 static final int TREEIFY_THRESHOLD = 8; 树化阈值 static final int UNTREEIFY_THRESHOLD = 6; 树降级阈值 static final int MIN_TREEIFY_CAPACITY = 64; 树化阈值 transient Node<K,V>[] table; 哈希表 transient Set<Map.Entry<K,V>> entrySet; 键值对对象集合 transient int size; 元素长度 transient int modCount; 增删元素次数 int threshold;扩容阈值 扩容阈值=loadFactor*capacity final float loadFactor; 负载因子核心方法

put–>putVal(存储数据)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //判断表是否为空或长度为0,若满足条件,则初始化表(体现了延迟加载) if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //判断要添加的元素对应的列是否为空,若满足条件,则直接插入 if ((p = tab[i = (n – 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //判断元素的哈希值与要存储列的键相同,则替换键对应的值 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) //如果当前节点是一个数结构节点,按照树结构存储新元素。 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { //遍历当前列的节点,判断如果当前节点超过8个节点,则将当前列转为树结构。 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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; }

resize(扩容)

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; }

tableSizeFor(数组长度初始化)

二进制位运算 右移:二进制数据向右移动一位,最高位补原最高位值,原最低位舍弃。4>>1结果等于2 2>>1结果等于1 无符号右移:二进制数据向右移动一位,最高位补0,原最低位舍弃。4>>>1结果等于2 2>>>1结果等于1 无符号右移动,会确保移动后一定是一个正数。 左移:二进制数据向左移动一位,最低位补0,原最高位舍弃。举例:4<<1结果等于8 8<<1结果等于16 或:有1则1 1001|100结果为1100(12) static final int tableSizeFor(int cap) { //下列操作的最终目的保证了,最终的n值一定比cap大,且最接近满足+1后数组长度定义的数值(0,3,7,15,31,63…) 1001 100 int n = cap – 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }