[JavaSE 源码分析] 关于HashMap的个人理解
目录
HashMap是什么?Map是Java常用的一种存储数据的Key-Value结构,键值对
HashMap的底层数据结构是什么?Entry是Map的辅助数据结构,Map的底层结构是Entry数组 // 必定是2的倍数 transient Node<K,V>[] table;
table容量为什么必须是二的倍数?为了更方便的存取数据,通过位运算代替模运算 // 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; }
// 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冲突时,作为缓解手段 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冲突的方法
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计算元素的hashhashCode和自己高16位相异或 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
HashMap添加/更新元素
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取值
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删除元素
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在并发场景下可能存在哪些问题?数据丢失 数据重复 死循环
通过Debug来进一步理解HashMap环境
过程测试代码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)); } } 目标成果底层数据结构
扩容过程
Debug技巧关闭Debug时IDEA优化的类结构当开启该选项时,IDEA将参数隐藏,比如:next,newThr等 发现table存放jar路径因为在源码debug时,不仅我们个人在使用HashMap,运行程序系统也会使用到它,所以我们可能会捕捉到系统在初始化时调用HashMap存取值
参考文章
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |