Java HashMap 学习笔记详细版一、HashMap 概述HashMap是 Java 集合框架中Map接口的最常用实现类基于**哈希表Hash Table**数据结构实现。核心特点键值对存储存储Key-Value映射Key 唯一Value 可重复。允许 nullKey 允许有一个nullValue 允许任意多个null。非线程安全多线程环境下数据可能不一致需使用ConcurrentHashMap或Collections.synchronizedMap。无序性不保证 Key 的遍历顺序注意不是完全随机而是基于哈希桶的分布。高性能在理想情况下get和put操作的时间复杂度为O(1)。二、底层数据结构与原理核心1. JDK 1.7 vs JDK 1.8 的区别特性JDK 1.7JDK 1.8底层结构数组 链表数组 链表 红黑树插入方式头插法(Head Insertion)尾插法(Tail Insertion)扩容时机先扩容后插入先插入后扩容 (检查阈值)哈希计算二次哈希 (扰动函数较复杂)简化扰动函数 (高位运算)死循环问题多线程扩容可能导致死循环解决了死循环问题 (尾插法)2. 核心参数table: 存储数据的数组Node 数组。size: 当前元素个数。threshold: 扩容阈值 capacity * loadFactor。loadFactor: 加载因子默认0.75。DEFAULT_INITIAL_CAPACITY: 默认初始容量16(必须是 2 的幂)。TREEIFY_THRESHOLD: 链表转红黑树阈值8。UNTREEIFY_THRESHOLD: 红黑树转链表阈值6。MIN_TREEIFY_CAPACITY: 树化最小数组容量64。3. 工作流程详解A. 哈希计算 (Hash)当调用put(key, value)时计算 Key 的hashCode()。进行扰动处理JDK 1.8(h key.hashCode()) ^ (h 16)。目的将高 16 位与低 16 位异或增加随机性减少哈希冲突。计算数组下标index (n - 1) hash。n是数组长度必须是 2 的幂。使用位运算代替%取模效率更高。B. 插入逻辑数组为空或位置为空直接新建 Node 放入。哈希冲突位置已有元素Key 相同(hash相同且equals为 true)覆盖旧 Value。Key 不同如果是链表尾插法添加到链表末尾。如果是红黑树按红黑树规则插入。链表转红黑树当链表长度 8且数组长度 64 时链表转为红黑树。如果数组长度 64优先进行扩容而不是转树。扩容 (Resize)当size threshold时触发。新容量 旧容量 * 2。JDK 1.8 优化重新计算下标时不需要重新计算 hash只需判断hash oldCap是否为 0。为 0位置不变。不为 0位置 原位置 旧容量。三、核心方法源码解析1. put 方法publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){NodeK,V[]tab;NodeK,Vp;intn,i;// 1. 如果数组为空或长度为0进行扩容if((tabtable)null||(ntab.length)0)n(tabresize()).length;// 2. 计算下标如果该位置为空直接插入if((ptab[i(n-1)hash])null)tab[i]newNode(hash,key,value,null);else{NodeK,Ve;Kk;// 3. 如果该位置第一个节点 Key 相同直接覆盖if(p.hashhash((kp.key)key||(key!nullkey.equals(k))))ep;// 4. 如果是红黑树节点按树逻辑插入elseif(pinstanceofTreeNode)e((TreeNodeK,V)p).putTreeVal(this,tab,hash,key,value);else{// 5. 如果是链表遍历插入尾插法for(intbinCount0;;binCount){if((ep.next)null){p.nextnewNode(hash,key,value,null);// 检查是否转红黑树if(binCountTREEIFY_THRESHOLD-1)treeifyBin(tab,hash);break;}if(e.hashhash((ke.key)key||(key!nullkey.equals(k))))break;pe;}}// 6. 如果找到了旧节点替换 Valueif(e!null){VoldValuee.value;if(!onlyIfAbsent||oldValuenull)e.valuevalue;afterNodeAccess(e);returnoldValue;}}modCount;// 7. 超过阈值扩容if(sizethreshold)resize();afterNodeInsertion(evict);returnnull;}2. get 方法publicVget(Objectkey){NodeK,Ve;// 调用 getNode 方法return(egetNode(hash(key),key))null?null:e.value;}finalNodeK,VgetNode(inthash,Objectkey){NodeK,V[]tab;NodeK,Vfirst,e;intn;Kk;// 1. 数组不为空且计算出的下标位置有元素if((tabtable)!null(ntab.length)0(firsttab[(n-1)hash])!null){// 2. 检查第一个节点if(first.hashhash// 总是检查 hash((kfirst.key)key||(key!nullkey.equals(key))))returnfirst;// 3. 如果还有下一个节点链表或树if((efirst.next)!null){// 如果是红黑树if(firstinstanceofTreeNode)return((TreeNodeK,V)first).getTreeNode(hash,key);// 如果是链表遍历查找do{if(e.hashhash((ke.key)key||(key!nullkey.equals(k))))returne;}while((ee.next)!null);}}returnnull;}四、关键机制详解1. 为什么 Key 要重写 hashCode 和 equalshashCode()决定元素在数组中的存储位置哈希桶。如果两个对象逻辑相等但 hashCode 不同它们会被放在不同的桶中导致get时找不到。equals()当哈希冲突hashCode 相同时用于判断两个 Key 是否真正相等。后果如果不重写默认使用 Object 类的实现基于内存地址导致逻辑上相同的对象被视为不同的 Key造成数据重复或无法获取。2. 为什么数组长度必须是 2 的幂计算下标优化(n - 1) hash等价于hash % n。只有当n是 2 的幂时n-1的二进制才是全 1如 15 - 1111此时位运算才能均匀分布。扩容优化扩容时元素要么留在原位置要么移动到原位置 旧容量无需重新计算 hash。3. 为什么加载因子是 0.75空间与时间的权衡太大哈希冲突概率增加链表变长查询效率下降趋向 O(n)。太小数组利用率低浪费空间频繁扩容。0.75 是统计学上的最佳平衡点泊松分布。4. 为什么链表长度 8 才转红黑树概率极低在随机 Hash 下链表长度达到 8 的概率极低约千万分之一。空间开销红黑树节点需要存储父节点、颜色等信息占用空间是普通 Node 的 2 倍。阈值 64如果数组长度小于 64说明空间还小优先扩容比转树更划算。五、使用示例1. 基本操作importjava.util.HashMap;importjava.util.Map;publicclassHashMapDemo{publicstaticvoidmain(String[]args){MapString,IntegermapnewHashMap();// 1. 添加map.put(Java,1);map.put(Python,2);map.put(Go,3);// 2. 获取System.out.println(map.get(Java));// 1System.out.println(map.get(C));// null// 3. 修改map.put(Java,100);// 覆盖System.out.println(map.get(Java));// 100// 4. 删除map.remove(Go);// 5. 遍历 (推荐 entrySet)for(Map.EntryString,Integerentry:map.entrySet()){System.out.println(entry.getKey() entry.getValue());}// 6. 判断包含System.out.println(map.containsKey(Python));// trueSystem.out.println(map.containsValue(100));// true// 7. 计算 (Java 8)map.computeIfAbsent(C,k-4);// 如果不存在则计算并放入System.out.println(map);}}2. 自定义 KeyclassStudent{intid;Stringname;publicStudent(intid,Stringname){this.idid;this.namename;}OverridepublicinthashCode(){returnid*31name.hashCode();}Overridepublicbooleanequals(Objecto){if(thiso)returntrue;if(onull||getClass()!o.getClass())returnfalse;Studentstudent(Student)o;returnidstudent.idname.equals(student.name);}}// 使用MapStudent,StringscoresnewHashMap();Students1newStudent(1,Alice);scores.put(s1,A);System.out.println(scores.get(newStudent(1,Alice)));// A六、常见问题与面试题Q1: HashMap 是线程安全的吗答不是。JDK 1.7多线程 put 可能导致死循环环形链表。JDK 1.8解决了死循环但可能导致数据覆盖丢失数据。解决方案使用ConcurrentHashMap推荐高性能。使用Collections.synchronizedMap(new HashMap())性能较差全表锁。Q2: HashMap 和 Hashtable 的区别特性HashMapHashtable线程安全否是 (synchronized)Null 支持Key/Value 均可 null均不可 null性能高低 (锁开销)继承实现 Map 接口继承 Dictionary (过时)推荐度推荐不推荐Q3: HashMap 和 ConcurrentHashMap 的区别HashMap非线程安全速度快。ConcurrentHashMap线程安全。JDK 1.7分段锁 (Segment)。JDK 1.8CAS synchronized(锁住链表/树的头节点)粒度更细并发度更高。Q4: 为什么 HashMap 的扩容是 2 的倍数为了利用位运算(n-1) hash快速计算下标。为了在扩容时快速重新定位元素原位置 或 原位置旧容量。Q5: 如果两个对象的 hashCode 相同会发生什么发生哈希冲突。HashMap 会将它们放在同一个数组下标桶中。形成链表或红黑树。插入时遍历链表调用equals()判断 Key 是否相同。相同覆盖 Value。不同挂在链表/树末尾。七、最佳实践设置初始容量如果知道大概的数据量设置初始容量避免频繁扩容。公式initialCapacity (expectedSize / 0.75) 1。例如预计存 10 个元素new HashMap(14)(10/0.75 13.33 - 14)。Key 必须不可变最好使用String、Integer等不可变类作为 Key。如果使用自定义对象确保hashCode和equals涉及的字段在放入 Map 后不被修改。遍历方式只遍历 KeykeySet()只遍历 Valuevalues()遍历 Key-ValueentrySet()(性能最好推荐)Java 8 Streammap.forEach((k, v) - ...)避免死锁多线程环境务必使用ConcurrentHashMap。八、总结HashMap是 Java 中最强大的数据结构之一其核心在于数组 链表 红黑树的混合结构兼顾了空间利用率和查询效率。哈希算法决定了分布的均匀性。扩容机制保证了动态增长时的性能。JDK 1.8 的优化尾插法、红黑树解决了死循环问题并提升了极端情况下的性能。掌握 HashMap 的底层原理是理解 Java 集合框架和应对高级面试的关键。