本文共 3157 字，大约阅读时间需要 10 分钟。

HashMap的特点

• HashMap基于Map接口实现，元素以键值对的方式存储
• 允许使用null键和null值，因为key不允许重复，因此只能有一个键为null
• HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同
• HashMap是线程不安全的（多线程环境中推荐ConcurrentHashMap或者通过Collections类的静态方法synchronizedMap获得线程安全的HashMap）

数据结构

• Java7以前使用数组+链表，Java8开始使用数组+链表+红黑树（效率从O(N)上升到O（LogN））
  HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，依次来解决Hash冲突的问题，因为HashMap是按照Key的hash值来计算Entry在HashMap中存储的位置的，如果hash值相同，而key内容不相等，那么就用链表来解决这种hash冲突。
  
  数组里存的是键（默认长度是16），链表里存放值
• 在java8以后引入常量TREEIFY_THRESHOLD来确定是否要把链表转化为红黑树

继承关系

public class HashMap
   
    extends AbstractMap
    
      implements Map
     
      , Cloneable, Serializable
     
    
   

基本属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16 static final float DEFAULT_LOAD_FACTOR = 0.75f;     //负载因子0.75static final Entry
   [] EMPTY_TABLE = {};         //初始化的默认数组transient int size;     //HashMap中元素的数量int threshold;          //判断是否需要调整HashMap的容量

构造方法

ashMap()    //无参构造方法HashMap(int initialCapacity)  //指定初始容量的构造方法 HashMap(int initialCapacity, float loadFactor) //指定初始容量和负载因子HashMap(Map
    m)  //指定集合，转化为HashMap

获取方法

public V get(Object key) {     if (key == null)         //返回table[0] 的value值         return getForNullKey();     Entry
   
     entry = getEntry(key);     return null == entry ? null : entry.getValue();}final Entry
    
      getEntry(Object key) {     if (size == 0) {         return null;     }     int hash = (key == null) ? 0 : hash(key);     for (Entry
     
       e = table[indexFor(hash, table.length)];         e != null;         e = e.next) {         Object k;         if (e.hash == hash &&             ((k = e.key) == key || (key != null && key.equals(k))))            return e;      }     return null;}
     
    
   

在get方法中，首先计算hash值，然后调用indexFor()方法得到该key在table中的存储位置，得到该位置的单链表，遍历列表找到key和指定key内容相等的Entry，返回entry.value值

• 若HashMap未被初始化，则进行初始化操作
• 对key求Hash值，依据Hash值计算下标
• 若未发生碰撞，则直接放入桶中
• 若发生碰撞。则以链表的方式链接到后面（JAVA8以后使用尾插法，方便转换成红黑树）
• 若链表长度超过阈值（默认为8），且HashMap元素超过最低树化容量（默认64），则将链表转化为红黑树
• 若结点已经存在，替换旧值
• 若桶满了，resize后重排

删除方法

public V remove(Object key) {     Entry
   
     e = removeEntryForKey(key);     return (e == null ? null : e.value);}final Entry
    
      removeEntryForKey(Object key) {     if (size == 0) {         return null;     }     int hash = (key == null) ? 0 : hash(key);     int i = indexFor(hash, table.length);     Entry
     
       prev = table[i];     Entry
      
        e = prev;     while (e != null) {         Entry
       
         next = e.next;         Object k;         if (e.hash == hash &&             ((k = e.key) == key || (key != null && key.equals(k)))) {             modCount++;             size--;             if (prev == e)                 table[i] = next;             else                 prev.next = next;             e.recordRemoval(this);             return e;         }         prev = e;         e = next;    }    return e;}
       
      
     
    
   

删除操作，先计算指定key的hash值，然后计算出table中的存储位置，判断当前位置是否Entry实体存在，如果没有直接返回，若当前位置有Entry实体存在，则开始遍历列表。定义了三个Entry引用，分别为pre, e ,next。 在循环遍历的过程中，首先判断pre 和 e 是否相等，若相等表明，table的当前位置只有一个元素，直接将table[i] = next = null 。若形成了pre -> e -> next 的连接关系，判断e的key是否和指定的key 相等，若相等则让pre -> next ,e 失去引用

转载地址：http://drqen.baihongyu.com/