HashMap源码及原理详解

目录

• HashMap概要
  
• 基本属性
  
• Node节点源码
  
• TreeNode节点源码
  
• 容量初始化
  
  
  
  • 容量为2的幂次方的好处
    
  
  
• 哈希的计算
  
• 哈希冲突
  
• put - 添加元素
  
• get - 获取元素
  
• resize - 数组扩容
  
  
  
  • JDK 1.8优化了key的哈希计算过程
    
  • JDK 1.8的尾插的优化，解决环形链表问题
    
  • JDK 1.7头插法扩容和环形链表问题
    
  
  
• 参考：
  

HashMap概要

代码如果没有特定说明，为JDK 1.8

• HashMap用来存放键值对，是Map接口的实现，是非线程安全的
  
• 可以存储key和value为null的值，但key为null的节点只能有一个
  
• 哈希值的计算：在hashCode的基础上添加扰动函数，使元素分布更加随机
  
• 哈希冲突：通过链表存储具有相同索引的元素，JDK1.8引入红黑树解决链表过长查询效率慢的问题
  
• 容量：
  
  
  
  • 总是以2的幂次方作为哈希表大小，用于优化key的哈希值的计算过程，默认初始容量为16；
    
  • 2倍扩容，JDK 1.8优化了key的数组下标的计算过程；JDK 1.8使用尾插法代替头插法，避免循环链表问题
    
  
  

JDK1.8 HashMap数据结构图

基本属性

[code]public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {    // 序列号    private static final long serialVersionUID = 362498820763181265L;    // 默认的初始容量是16    static final int DEFAULT_INITIAL_CAPACITY = 1