HashMap实现原理详解

我不是女神ヾ 2022-06-09 05:50 195阅读 0赞

1.  HashMap定义  
    HashMap实现了Map接口，一种将键映射到值得对象。  
    一个映射不能包含重复的键；每个键只能映射到一个值上。  
    HashMap的元素是无序的。要实现有序排列必须实现hashcode()方法和equals()方法。
2.  HashMap的继承关系。

public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable

HashMap继承了AbstractMap，实现了Map接口。

1.  HashMap的实现原理
    
    1.HashMap的存放采用线性表的存储方式。  
    线性表的大小会根据你给出的大小，由系统自动分配给你响应的空间。  
    实际上分配的是2的次方大小。(例如：你给了5个值，系统会自动分配给你2的3次方也就是8)  
    2.每个值存放的是键值对，也就是Entry

static class Entry<K,V> implements Map.Entry<K,V> {
        
            final K key;
            V value;
            Entry<K,V> next;
            int hash;
    }

用图解释他的存放原理。  
1. HashMap存放的是键值对。也就是Entry。 其中key和value分别对应了其中的键和值。next存放的是下一个的地址。其中hash是由key进过hashcode()方法进行计算，得到的hash值。  
2. 然后再进行散列计算。散列计算大体上来说就是进行求余计算。根据系统分配的大小。用这个大小进行求余计算，然后根据求余结果存放到相应的位置。然后进行equals方法进行判断。如果没有值和他相等。就放在整个链表的首部位置。  
3.其中，有一个加载因子的问题。也就是说，没次系统分配内存大小时。都会根据2的几次方再乘以加载因子的大小。取值为0<=p<=1.  
每次当线性表填满时。他会进行扩容。也就是乘以2。这是内存大小发生变化，就会进行reHash操作。然后重新分配相应的位置。加载因子的大小最好为0.75。  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220609/dea894ba54a340989283817b96d6bf05.png