当前位置：首页>编程日记>正文

集合框架知识系列05 HashMap的源码分析和使用示例

编程日记 2024/08/02 19:21:01

本站寻求有缘人接手，详细了解请联系站长QQ1493399855

一、HashMap简介

HashMap是基于“拉链法”实现的散列表。一般用于单线程程序中，JDK 1.8对HashMap进行了比较大的优化，底层实现由之前的“数组+链表”改为“数组+链表+红黑树”。下面先介绍HashMap中一些关键的知识点。

1、哈希表

哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。下面是百度百科中的一张哈希表示例：
集合框架知识系列05 HashMap的源码分析和使用示例 配图01
常用的散列方法有： 直接寻址法：取关键字或关键字的某个线性函数值为散列地址、数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同、平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。

2、红黑树

红黑树是一颗自平衡的二叉查找树，除了符合二叉查找树的特定，还有一下一些特点：

  • 节点是红色或黑色。
  • 根节点是黑色。
  • 每个叶子节点都是黑色的空节点（NIL节点）。
  • 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下面是一棵红黑树的示例图：

集合框架知识系列05 HashMap的源码分析和使用示例 配图02

3、HashMap中的节点结构

HashMap中通过实现Map.Entry<K,V>接口作为哈希表节点的，具体代码如下：

static class Node<K,V> implements Map.Entry<K,V> {//hash值final int hash;//map中的keyfinal K key;//map中的值V value;//指向的下一个节点，用于hash表中的链表 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; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}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;}}

另外，通过定义继承LinkedHashMap.Entry<K,V> 来定义TreeNode<K,V>作为红黑树的节点，具体代码在下一节介绍。

二、源码分析

HashMap继承自AbstractMap，并且实现了Map、Cloneable和Serializable接口，具体的源码分析如下：

public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable{/*** 默认初始化容量大小，必须是2的次幂*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;/*** 最大的容量*/static final int MAXIMUM_CAPACITY = 1 << 30;/*** 默认负载因子.*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** 链表节点转红黑树节点的阈值，9个节点时转*/static final int TREEIFY_THRESHOLD = 8;/*** 红黑树节点转为链表的阈值，6个节点时转*/static final int UNTREEIFY_THRESHOLD = 6;/*** 链表节点转红黑树节点时，哈希表达最小节点为64*/static final int MIN_TREEIFY_CAPACITY = 64;/*** 链表节点结构*/static class Node<K,V> implements Map.Entry<K,V> {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; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}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;}}/* ---------------- 静态公用方法 -------------- *//*** 对hashCode的hash计算如总结中图所示：* 在设计hash函数时，因为目前的table长度n为2的次幂，所以计算下标的时候，可使用按位与&代替取模%：(n - 1) & hash。* 设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。* 设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。* 仅仅异或一下，既减少了系统的开销，也不会造成因为高位没有参与下标的计算(table长度比较小)时，引起的碰撞。*//***计算hash值，根据key的hashCode计算*/static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}/*** 如果对象实现了Comparable接口，则返回其Class对象*/static Class<?> comparableClassFor(Object x) {if (x instanceof Comparable) {Class<?> c; Type[] ts, as; Type t; ParameterizedType p;if ((c = x.getClass()) == String.class) // bypass checksreturn c;if ((ts = c.getGenericInterfaces()) != null) {for (int i = 0; i < ts.length; ++i) {if (((t = ts[i]) instanceof ParameterizedType) &&((p = (ParameterizedType)t).getRawType() ==Comparable.class) &&(as = p.getActualTypeArguments()) != null &&as.length == 1 && as[0] == c) // type arg is creturn c;}}}return null;}/*** 如果x和kc匹配，返回k.compareTo(x)，否则返回0。*/@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparablestatic int compareComparables(Class<?> kc, Object k, Object x) {return (x == null || x.getClass() != kc ? 0 :((Comparable)k).compareTo(x));}/*** 根据给定的容量大小，返回一个2的次幂大小的值。比如，cap=7，返回8*/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;}/* ---------------- 成员变量 -------------- *//*** 哈希表定义，在第一次使用时初始化*/transient Node<K,V>[] table;/*** 节点缓存*/transient Set<Map.Entry<K,V>> entrySet;/*** map中含有key-value的大小*/transient int size;/*** 修改次数*/transient int modCount;/*** 下次要调整容量的大小 (capacity * load factor).*/int threshold;/*** 哈希表的负载因子*/final float loadFactor;/* ---------------- 公共操作 -------------- *//*** 给定初始化容量和负载因子的构造方法*/public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);}/*** 给定初始化大小的构造函数*/public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}/*** 无参构造方法*/public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}/*** 通过给定的map构造一个hashmap，负载因子是0.75*/public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}/*** 此方法是先构造一个hashMap对象，调用putVal方法将m中的元素入新map**/final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {//m的大小int s = m.size();if (s > 0) {//table没有初始化，先计算threshold if (table == null) { // pre-size//获取容量初始大小,+1可以节省一次resizefloat ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);//计算threshold if (t > threshold)threshold = tableSizeFor(t);}//如果threshold小于s,调整大小else if (s > threshold)resize();//调用 putVal将m中的节点元素入此hashmapfor (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();putVal(hash(key), key, value, false, evict);}}}/*** 返回map中key-value中的数量*/public int size() {return size;}/*** 返回map中key-value中的数量是否为0*/public boolean isEmpty() {return size == 0;}/*** 通过key获取一个节点元素，如果不存在，返回null**/public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;}/*** Map.get的实现方法*/final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//如果table不为空，且长度大于0、通过hash能找到第一个节点if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//检查第一个节点，判断key是否相等if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//如果有下一个节点if ((e = first.next) != null) {//判断是否为红黑树节点，如果是，调用getTreeNode方法获取节点元素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;}/*** 返回map中是否包含key*/public boolean containsKey(Object key) {return getNode(hash(key), key) != null;}/*** 调用putVal方法，添加一个节点*/public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*** Map.put的实现方法** @param hash hash for key* @param key the key* @param value the value to put* @param onlyIfAbsent 如果是true,不替换已存在value* @param evict if false, the table is in creation mode.* @return previous value, or null if none*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//如果table为空，或者大小为0，调用resize方法if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//hash后，如果此位置的节点为null,则新建节点，赋值到此位置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;//如果此节点时红黑树节点，调用红黑树putTreeVal方法添加节点else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {//到最后一个节点，新建此节点，并且检查是否转换为红黑树if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//根据onlyIfAbsent 判断是否需要替换valueif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//size+1if (++size > threshold)resize();afterNodeInsertion(evict);return null;}/*** 数组初始化或者加倍* @return the table*/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}//如果原阈值大于0，则新阈值就是原阈值else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//否则，新阈值和新容量都默认else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//如果新阈值为0，通过加载因子和新容量计算新阈值if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//将新阈值赋值threshold threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})//定义新的数组Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//table指向新的数组table = newTab;//如果原数组为空，直接返回新定义数组，第一次put时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)//hash到新表newTab[e.hash & (newCap - 1)] = e;//判断是否为红黑树节点，如果是，调用split方法处理else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<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，如果这个表达式为true,则(e.hash & (oldCap - 1))* 和(e.hash & (newCap - 1))值是一样的，说明节点的位置没有发生变化。这样做的原因是oldCap和newCap都是* 2的次幂，并且newCap是oldCap的2倍，表示oldCap转换为二进制的唯一一个1向高位移位一次。下面举例说明：* 比如，oldCap=16，则newCap=32。如果(e.hash & oldCap) == 0，* 因为e.hash & 0x10000 == 0, e.hash & 0x100000 == 0,现在e.hash的位置是由e.hash & 0x1111确定，* 则e.hash & 0x11111 的值也是一样的。根据这一个二进制位就可以判断下次hash定位在* 哪里了。将hash冲突的元素连在两条链表上放在相应的位置*///将位置不变的节点放到链表loHead if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}//将位置变化的节点，放到链表hiHeadelse {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//将loHead放到新表位置if (loTail != null) {loTail.next = null;newTab[j] = loHead;}//将hiHead放到新表位置if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}}

三、使用示例

1、重写equals时也要同时重写hashCode

在HashMap中，作为key的对象，如果重写了equals方法，hashCode也要覆盖重写，下面通过一个例子说明不重写会出现什么问题：

public class HashMapTest {public static void main(String[] args) {Dog dog = new Dog("test1", 1);Cat cat = new Cat("test2", 2);Map<Dog, String> map1 = new HashMap<>(1);map1.put(dog, "测试1");Map<Cat, String> map2 = new HashMap<>(1);map2.put(cat, "测试2");System.out.println("没有重写hashCode方法：" + map1.get(new Dog("test1", 1)));System.out.println("重写hashCode方法：" + map2.get(new Cat("test2", 2)));}/*** 只重写了equals方法*/static class Dog {private String name;private Integer id;public Dog(String name, Integer id){this.name = name;this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public Integer getId() {return id;}public void setId(Integer id) {this.id = id;}@Overridepublic boolean equals(Object obj) {if (this == obj){return true;}if (obj == null || obj.getClass() != this.getClass()){return false;}Dog dog = (Dog) obj;return (this.id != null) && (this.id.equals(dog.id));}}/*** 重写了equals和hashCode方法*/static class Cat {private String name;private Integer id;public Cat(String name, Integer id){this.name = name;this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public Integer getId() {return id;}public void setId(Integer id) {this.id = id;}@Overridepublic boolean equals(Object obj) {if (this == obj){return true;}if (obj == null || obj.getClass() != this.getClass()){return false;}Cat cat = (Cat) obj;return (this.id != null) && (this.id.equals(cat.id));}@Overridepublic int hashCode() {if (this.id == null){return 0;}return this.id;}}
}

上述代码运行结果如下：

集合框架知识系列05 HashMap的源码分析和使用示例 配图03

可以看到，没有重写hashCode方法的对象作为key,查询得到的是null，因为两个对象的hashCode的并不一致，所以导致取到的是null。

2、HashMap的遍历方式

HashMap提供了对key-value、key、value等多种遍历方式，下面通过一个示例演示其用法：

public class HashMapIteratorTest {public static void main(String[] args) {Map<String, String > map = new HashMap<>();for (int i = 0; i < 10; i++) {map.put(String.valueOf(i), String.valueOf(i));}entrySetForeach(map);entrySetIterator(map);keySet(map);valueSet(map);foreachJdk8(map);}/*** 获取Map.Entry，然后遍历key 和value，通过foreach遍历* @param map*/static void entrySetForeach(Map<String , String > map){for (Map.Entry<String , String> entry: map.entrySet()) {System.out.print("key:" + entry.getKey() + ",value:" + entry.getValue() + "----");}System.out.println();}/*** 获取Map.Entry，然后遍历key 和value，通过Iterator遍历* @param map*/static void entrySetIterator(Map<String , String > map){Iterator<Map.Entry<String , String>> iterator = map.entrySet().iterator();while (iterator.hasNext()){Map.Entry<String , String> entry = iterator.next();System.out.print("key:" + entry.getKey() + ",value:" + entry.getValue() + "----");}System.out.println();}/*** 获取keySet,遍历key,同样支持foreach和Iterator遍历，只实现foreach* @param map*/static void keySet(Map<String , String > map){for (String string: map.keySet()) {System.out.print("key:" + string + "----");}System.out.println();}/*** 获取values,遍历value,* @param map*/static void valueSet(Map<String , String > map){for (String string: map.values()) {System.out.print("value:" + string + "----");}System.out.println();}static void foreachJdk8(Map<String , String > map){map.forEach((k, v)-> System.out.print("key:" + k + ",value:" + v + "----"));System.out.println();}
}

四、总结

  1. 在HashMap的使用中，建议设置已知的大小，因为在扩容的时候，resize方法要重建hash表，严重影响性能。

  2. HashMap定义和扩展中，大小必须为2的次幂，这样做的原因如下：

    a、计算位置时：(n - 1) & hash可以实现一个均匀分布。b、hash%length==hash&(length-1)的前提是length是2的次幂。length是2次幂时，可以用以为代替取模，提高效率。

  3. 扩容过程中会新数组会和原来的数组有指针引用关系，所以将引起死循环问题。JDK1.8中已经解决这个问题了。

对hashCode的hash计算

集合框架知识系列05 HashMap的源码分析和使用示例 配图04


http://www.coolblog.cn/news/586e18935c1794a8.html

相关文章：

  • asp多表查询并显示_SpringBoot系列（五）：SpringBoot整合Mybatis实现多表关联查询
  • s7day2学习记录
  • 【求锤得锤的故事】Redis锁从面试连环炮聊到神仙打架。
  • 矿Spring入门Demo
  • 拼音怎么写_老师：不会写的字用圈代替，看到孩子试卷，网友：人才
  • Linux 实时流量监测(iptraf中文图解)
  • Win10 + Python + GPU版MXNet + VS2015 + RTools + R配置
  • 美颜
  • shell访问php文件夹,Shell获取某目录下所有文件夹的名称
  • 如何优雅的实现 Spring Boot 接口参数加密解密？
  • LeCun亲授的深度学习入门课：从飞行器的发明到卷积神经网络
  • 法拉利虚拟学院2010 服务器,法拉利虚拟学院2010
  • Mac原生Terminal快速登录ssh
  • 支撑微博千亿调用的轻量级RPC框架：Motan
  • mysql commit 机制_1024MySQL事物提交机制
  • java受保护的数据与_Javascript类定义语法,私有成员、受保护成员、静态成员等介绍...
  • 2019-9
  • jquery 使用小技巧
  • vscode pylint 错误_将实际未错误的py库添加到pylint白名单
  • 科学计算工具NumPy（3）：ndarray的元素处理
  • 工程师在工作电脑存 64G 不雅文件，被公司开除后索赔 41 万，结果…
  • linux批量创建用户和密码
  • js常用阻止冒泡事件
  • 气泡图在开源监控工具中的应用效果
  • newinsets用法java_Java XYPlot.setInsets方法代碼示例
  • 各类型土地利用图例_划重点！国土空间总体规划——土地利用
  • php 启动服务器监听
  • dubbo简单示例
  • Ubuntu13.10：[3]如何开启SSH SERVER服务
  • [iptables]Redhat 7.2下使用iptables实现NAT
  • Django View（视图系统）
  • 【设计模式】 模式PK：策略模式VS状态模式
  • JS实现-页面数据无限加载
  • CSS小技巧——CSS滚动条美化
  • 最新DOS大全
  • 阿里巴巴分布式服务框架 Dubbo
  • Sorenson Capital：值得投资的 5 种 AI 技术
  • 阿里大鱼.net core 发送短信
  • 程序员入错行怎么办？
  • Arm芯片的新革命在缓缓上演
  • 两张超级大表join优化
  • 第九天函数
  • 通过Spark进行ALS离线和Stream实时推荐
  • HDU 5988 最小费用流
  • Linux软件安装-----apache安装
  • 《看透springmvc源码分析与实践》读书笔记一
  • nagios自写插件—check_file
  • python3 错误 Max retries exceeded with url 解决方法
  • 正式开课！如何学习相机模型与标定？（单目+双目+鱼眼+深度相机）
  • 行为模式之Template Method模式