目录
HashMap是什么?
Map是Java常用的一种存储数据的Key-Value结构,键值对
HashMap是Map结构,底层采用Hash算法存取Key值
HashMap: 基于哈希表的 Map 接口的实现.
HashMap的底层数据结构是什么?
Entry是Map的辅助数据结构,Map的底层结构是Entry数组
但处理hash冲突使用链表法,使用链表的方式存储冲突元素
当某位置上的冲突数据累计到一定程度上时,会转化成红黑树结构
// 必定是2的倍数 transient Node<K,V>[] table;
HashMap的底层数据结构是数组和链表 用于存放元素
当某位置上元素个数大于等于8(并且table大小大于64)时 链表转换成红黑树结构 TREEIFY_THRESHOLD=8if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab,hash)
元素个数小于6时 红黑树结构转换成链表结构 UNTREEIFY_THRESHOLD=6if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map)
数组的特点是: 寻址容易,插入和删除困难
链表的特点是: 寻址困难,插入和删除容易
红黑树: 自平衡的二叉查找树,查找效率是非常的高,查找效率会从链表的o(n)降低为o(logn)
table容量为什么必须是二的倍数?
为了更方便的存取数据,通过位运算代替模运算
hash&(n-1)就是它的存放位置
// index 为元素在table数组中存放位置 // n = table.length // hash 为key的hash index = (n - 1) & hash; // 有可能1都集中在前16位中 // 而导致明明相差很大的数据 因为后16位相同而发生冲突 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 右位移16位,正好是32bit的一半,自己的高半区和低半区做异或,// 就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性. // 而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来.
table容量怎么做到二的倍数?
通过右移和或位运算的方式 得到大于等于输入参数的最小2的倍数
/** * 返回大于等于给定参数的值(2的倍数) * 首位为1 其余为0 * cap最大为: 1 << 30 * * 先求全1 再加1 --> 1111 + 1 = 1 0000 */ static final int tableSizeFor(int cap) { 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; }
- 为什么要对cap做减1操作?
这是为了防止,cap已经是2的幂. 如果cap已经是2的幂,又没有执行这个减1操作,则执行完后面的几条无符号右移操作之后,返回的capacity将是这个cap的2倍.
- 因为输入参数不为0 则必有1bit为1 最高位为1
第一次右移: 最高位和次高位 最高位必为1
第二次右移: 前两位和前三四位 前两位必为1
第三次右移: 前四位和前5~8位 前四位必为1
...
最高位以下全为1
- 最终该值被赋予threshold 只是临时存储 在resize()初始化时
// initial capacity was placed in threshold else if (oldThr > 0) newCap = oldThr;
Entry是怎样的结构?
Entry是单个键值对,提供简单的key,value的操作方式
interface Entry<K,V> { // 返回该实例存储的Key K getKey(); // 返回该实例存储的Value V getValue(); // 替换该实例存储的value // 返回原有value值 V setValue(V value); // 判断两实例相等的方法 // 一般指定两者的Key,Value均要相等 boolean equals(Object o); // 获取该实例的hashCode // 一般为该实例的唯一标识 int hashCode(); // 返回一个比较Entry key值的比较器 public static <K extends Comparable<? super K>,V> Comparator<Map.Entry<K,V>> comparingByKey() { return (Comparator<Map.Entry<K,V>> & Serializable) (c1,c2) -> c1.getKey().compareTo(c2.getKey()); } // 返回一个比较Entry value值的比较器 public static <K,V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() { return (Comparator<Map.Entry<K,c2) -> c1.getValue().compareTo(c2.getValue()); } // 通过给进比较key值的比较器 来获得一个比较Entry的比较器 public static <K,V>> comparingByKey(Comparator<? super K> cmp) { Objects.requireNonNull(cmp); return (Comparator<Map.Entry<K,c2) -> cmp.compare(c1.getKey(),c2.getKey()); } // 通过给进比较value值的比较器 来获得一个比较Entry的比较器 public static <K,V>> comparingByValue(Comparator<? super V> cmp) { Objects.requireNonNull(cmp); return (Comparator<Map.Entry<K,c2) -> cmp.compare(c1.getValue(),c2.getValue()); } }
Node: Entry在HashMap中的具体实现
Node是个链表节点结构,主要用途在处理hash冲突时,作为缓解手段
(计算hash得出的存储位置上已经有元素,则将该元素作为上一元素的下一节点)
static class Node<K,V> implements Map.Entry<K,V> { // hash,key一般赋值后不能被修改 final int hash; final K key; V value; // 存放下一节点 Node<K,V> next; Node(int hash,K key,V value,Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } // 该Node实例的hashCode是key的hashCode和value的hashCode相异或 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // key,value都相等 public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key,e.getKey()) && Objects.equals(value,e.getValue())) return true; } return false; } }
处理hash冲突的方法
- 开放定址法
一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入 - 链地址法
将哈希表的每个单元作为链表的头结点,所有哈希地址为index的元素构成一个同义词链表.
即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部 - 再哈希法
当哈希地址发生冲突用其他的函数计算另一个哈希函数地址,直到冲突不再产生为止 - 建立公共溢出区
将哈希表分为基本表和溢出表两部分,发生冲突的元素都放入溢出表中
HashMap初始化或扩容 resize()
/** * 初始化或数组容量翻倍 */ final Node<K,V>[] resize() { // 获得原有全局表 table Node<K,V>[] oldTab = table; // 获得原有表的容量 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获得原有表的阈值 容量*负载因子 // 如果设置了初始容量 threshold等于设置的初始容量(大于等于输入参数的最小的二倍数) // 如果没有则为0 int oldThr = threshold; // 设置新表的容量和阈值 int newCap,newThr = 0; // 如果原有表不为空 if (oldCap > 0) { // 如果原有表的容量大于等于最大容量 不用扩展 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; // 如果旧表的容量 大于16 翻倍后小于最大容量 } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 新表的阈值也是旧表阈值的两倍 newThr = oldThr << 1; // 如果旧表为空 并且事先设置了参数 threshold不为空 } else if (oldThr > 0) // 使用初始化的旧表阈值做新表的容量 newCap = oldThr; // 旧表为空 没有设置参数 threshold为空 else { // 新表容量 使用默认初始容量 16 newCap = DEFAULT_INITIAL_CAPACITY; // 新表阈值为 16*0.75 = 12 newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 以上就处理完 新表的参数 容量newCap // 此时 旧表为空 并且设置了参数 threshold不为空 if (newThr == 0) { // 使用新表的容量计算新表的阈值 float ft = (float) newCap * loadFactor; // 新表的容量小于最大容量 计算的新表阈值也小于最大容量 则获得新表阈值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } // 以上就处理完 新表的参数 容量newCap和阈值newThr 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; // 如果该位置只有一个Node 没有下一Node if (e.next == null) // 通过indexFor存入新表中 newTab[e.hash & (newCap - 1)] = e; // 判断该位置Node的链接Node是什么结构? // 树形结构 红黑树 else if (e instanceof TreeNode) ((TreeNode<K,V>) e).split(this,newTab,j,oldCap); // 链状结构 链表 else { // head 指向链表头部 tail 构建整个链表 Node<K,V> loHead = null,loTail = null; Node<K,V> hiHead = null,hiTail = null; Node<K,V> next; do { // 先取到该位置的下一节点 next = e.next; // e.hash & oldCap = 0 则该Node不需要移位 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; }
HashMap计算元素的hash
hashCode和自己高16位相异或
如此使得hash更离散 使得元素分布的更均匀
一般我们的容量都比较小,2^16
而计算元素key值位置是hash&(n-1)
基本只有低几位信息是有效的 如此的hash冲突比较大
如果将高位的信息也参与运算 可以一定程度上缓解冲突
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
设计者将key的哈希值的高位也做了运算(与高16位做异或运算,使得在做&运算时,此时的低位实际上是高位与低位的结合),这就增加了随机性,减少了碰撞冲突的可能性
HashMap添加/更新元素
- 先检查table是否被初始化 没有则先resize() 初始化
- 通过hash&(n-1)获取存放位置 如果该位置为空 则存储元素
- 发生hash冲突,查找该位置的key值相等的元素 没有则添加元素到尾部/叶子节点
- 查找到key值相等的元素 更新其value值,返回旧值
public V put(K key,V value) { return putVal(hash(key),key,value,false,true); } final V putVal(int hash,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; // i = (n - 1) & hash 通过位运算得到需要存放的位置 // 如果该位置为空 则直接存储 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash,null); // 发生hash冲突 else { // 获取存放位置的元素 Node<K,V> e; K k; // p 是已存放元素 // 判断p是否与将要存放的元素key相等 // 如果key相等 表示是更新元素 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // key不相等 并且p为树状结构节点 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this,tab,hash,value); // key不相等 并且p为链状结构节点 else { for (int binCount = 0; ; ++binCount) { // 找到最后一个节点 if ((e = p.next) == null) { // 添加节点 p.next = newNode(hash,null); // 如果该链表长度大于等于7 则转化为红黑树结构 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab,hash); break; } // 继续判断查询节点是否与将要存放的元素key相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 如果存放的位置不为空 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 如果表格元素个数大于阈值 则扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
HashMap取值
- 判断table是否为空 为空则返回null
- 检查hash&(n-1)的位置是否为空 为空则返回null
- 判断首位元素是否符合要求 满足则返回该元素
- 发生hash冲突,查看该位置其他节点 找到就返回该元素 没有则返回null
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> first,e; int n; K k; // 当table不为空 并且hash位置上存有元素 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 检查该位置的第一个元素 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 如果第一个元素 不符合查询条件 // 则表示有可能是hash冲突 if ((e = first.next) != null) { // 如果首位元素是树节点 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash,key); // 首位元素是链表节点 遍历 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
HashMap删除元素
- 判断table是否为空 为空则返回null
- 同getNode(hash,key)一样过程 先根据key值查找符合条件的元素
- 找到该元素再将其删除,并返回该元素
public boolean remove(Object key,Object value) { return removeNode(hash(key),true,true) != null; } final Node<K,V> removeNode(int hash,Object key,Object value,boolean matchValue,boolean movable) { Node<K,index; // 判断table是否为空 并且hash位置上存有元素 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null,e; K k; V v; // 以下为找出符合要求的元素 根据key值 "getNode(hash,key)" // 首位元素 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; // 发生hash冲突 该位置其他节点 else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash,key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } // 找打符合要求的元素node // matchValue 表示是否需要匹配value值 false表示不用 即使输入value不对 也可以删除该元素 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this,movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }
HashMap为什么是非线程安全的?
因为里面的方法都不是线程安全的
HashMap在并发场景下可能存在哪些问题?
数据丢失 数据重复 死循环
- Doug Lea writes:
通过上面Java7中的源码分析一下为什么会出现数据丢失,如果有两条线程同时执行到这条语句 table[i]=null 时两个线程都会区创建Entry,这样存入会出现数据丢失.
如果有两个线程同时发现自己都key不存在,而这两个线程的key实际是相同的,在向链表中写入的时候第一线程将e设置为了自己的Entry,而第二个线程执行到了e.next,此时拿到的是最后一个节点,依然会将自己持有是数据插入到链表中,这样就出现了
数据重复
.
通过put源码可以发现,是先将数据写入到map中,再根据元素到个数再决定是否做resize.
在resize过程中还会出现一个更为诡异的问题死循环.
这个原因主要是因为hashMap在resize过程中对链表进行了一次倒序处理.
假设两个线程同时进行resize,A->B 第一线程在处理过程中比较慢,第二个线程已经完成了倒序编程了B-A 那么就出现了循环,B->A->B.这样就出现了就会出现cpu使用率飙升.
PS:在这个过程中可以发现,之所以出现死循环,主要还是在于对于链表对倒序处理,在Java 8中,已经不在使用倒序列表,死循环问题得到了极大改善.
通过Debug来进一步理解HashMap
环境
- IntelliJ IDEA 2018 专业版
- Deepin Linux 15.9桌面版
过程
测试代码
import java.util.HashMap; import java.util.Map; import java.util.Objects; import java.util.Random; /** * 通过debug查看HashMap存储数据时的结构 * * @author lingsh * @version 1.0 * @date 19-9-25 下午4:29 */ public class TestHashMap { public static void main(String[] args) { // size 存放数据量 // cap HashMap初始设置容量 10 --> 16 int size = 10000,cap = 10; Map<THMString,Integer> map = new HashMap<>(cap); // 存放数据 for (int i = 0; i < size; i++) { map.put(THMString.getRandomString(),i); } // 用于定点调试(只是该main函数的终止位置,可以用于暂停查看map结构) System.out.println(map.size()); } } /** * TestHashMapString * hashCode分布极其集中的自定义类 * 底层是LEN大小的字符串 */ class THMString { /** * 底层真实数据 */ private String str; /** * SIZE 用于加强实例碰撞的可能性 */ private final static int SIZE = 1024; /** * 底层数据大小 */ private final static int LEN = 5; /** * 使用随机数来确定底层数据内容 */ private static Random random = new Random(); public THMString(String str) { this.str = str; } @Override public int hashCode() { // 集中hashCode 通过不断的取余来加强碰撞可能 return str.hashCode() % SIZE % SIZE % SIZE % SIZE % SIZE; } @Override public boolean equals(Object obj) { THMString thms = (THMString) obj; return Objects.equals(this.str,thms.str); } @Override public String toString() { return "[String:" + str + "\thashCode:" + hashCode() + "]"; } /** * 获取随机的实例作为HashMap的Key * * @return 随机的实例 */ static THMString getRandomString() { char[] chars = new char[LEN]; for (int i = 0; i < chars.length; i++) { int word = random.nextInt('z' - 'a'); chars[i] = (char) (word + 'a'); } return new THMString(new String(chars)); } }
目标成果
底层数据结构
- Node
- TreeNode
扩容过程
扩容开始时
扩容时移动一个节点到新表
Debug技巧
关闭Debug时IDEA优化的类结构
当开启该选项时,IDEA将参数隐藏,比如:next,newThr等
发现table存放jar路径
因为在源码debug时,不仅我们个人在使用HashMap,运行程序系统也会使用到它,所以我们可能会捕捉到系统在初始化时调用HashMap存取值
所以,建议
- 先给自己程序设断点,确定在开始自己的程序,再到HashMap源码那设置断点