HashMap详解

了解HashMap之前，我们要先了解Map和Hash表

什么是Map?

map就是用于存储键值对（<key,value>）的集合类，也可以说是一组键值对的映射（数学概念）。在java中map是一个接口，是和collection接口同一等级的集合根接口。

Map的存储结构：

下图就是Map的存储结构图，keyset（键的集合）和values（值的集合），每一条记录都是一个entry（一个键值对）。

Map的特点：

（1）没有重复的key，因为key是set保持的，是唯一的，无序的，如果key相同则会作为覆盖value处理。

（2）一个key只能对应一个value，一个value可以对应多个key，就好比射箭，很多人设一个靶子，每个人只能射这一个靶子，但是这个靶子可以让很多人射。

（3）key，value可以是任何的引用类型（包括null）

了解map接口之后，我们来了解一下hash表：

什么是Hash表？

在将键值对存入数组之前，将key通过哈希算法计算出哈希值，把哈希值作为数组下标，把该下标对应的位置作为键值对的存储位置，通过该方法建立的数组就叫做哈希表，而这个存储位置就叫做桶（bucket）。通俗一点讲就是顺序表和链表的组成（数组+单链表）

hash表的数据表现形式：数组+链表

Node<K,V> [] table;//数组，方便查找数据

class Node<K,V>{

final int hash;//hash值,查找或者删除，用来判断hash值是否相等

K key;//key，查找或者删除用来判断输入的key值是否相等（==或者equals）

V value;//value

Node<K,V> next;//指向的下一个节点

}

什么是HashMap?

HashMap是用哈希表（直接一点可以说数组加单链表）+红黑树实现的map类。

HashMap的存储结构：

HashMap的特点：

1、底层实现是链表数组，JDK 8 后又加了红黑树

2、实现了 Map 全部的方法

3、key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类（一般是String）需要重写 hashCode 和 equals 方法

4、允许空键和空值（但空键只有一个，且放在第一位，知道就行）

5、元素是无序的，而且顺序会不定时改变（每次扩容后，都会重新哈希，也就是key通过哈希函数计算后会得出与之前不同的哈希值，这就导致哈希表里的元素是没有顺序，会随时变化的，这是因为哈希函数与桶数组容量有关，每次结点到了临界值后，就会自动扩容，扩容后桶数组容量都会乘二，而key不变，那么哈希值一定会变）

6、插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置）

7、遍历整个 Map 需要的时间与数组的长度成正比（因此初始化时 HashMap 的容量不宜太大）

8、两个关键因子：初始容量（CAPACITY =16）、加载因子（loadFactor = 0.75）、阈值 threshold = CAPACITY * LoadFactor

9、HashMap不是同步，HashTable是同步的，但HashTable已经弃用，如果需要线程安全，可以用synchronizedMap，例如 Map m = Collections.synchronizedMap(new HashMap(...));

HashMap的源码解析：增删改查

1、构造方法：

//创建一个空的哈希表，初始容量为 16，加载因子为 0.75

public HashMap()

//创建一个空的哈希表，指定容量，使用默认的加载因子

public HashMap(int initialCapacity)

//创建一个空的哈希表，指定容量和加载因子

public HashMap(int initialCapacity, float loadFactor)

//创建一个内容为参数 m 的内容的哈希表

public HashMap(Map<? extends K, ? extends V> m)

2、增：public V put(K key,V value):

（1）判断key是否为空，如果是添加null key；

（2）通过hash()函数获取hash值；

（3）通过indexFor()函数找到hash值对应的table数组的下标index；注：

（4）从数组下标对应的节点开始用for循环，判断当前节点是否存在，存在返回oldValue；

（5）addEntry直接添加，modCount++；

注意：hash()方法获取的是hash值；indexFor()里面的返回：h&(length-1)与运算，相当于求余数。

3、public void addEntry(int hash,K key, V value,int bucketIndex)

（1）判断是否需要扩容，长度size大于阈值threshold并table数组下面不为空；扩容为table长度的两倍；重新获取hash值和table的脚标bucketIndex;

（2）创建节点

4、public void createEntry(int hash,K key,V value, int bucketIndex)：创建一个节点

(1)创建一个新的节点，放在表头；定义一个节点e=table[bucketIndex]；创一个新节点指向e;table[bucketIndex] =新节点。

5、public V get(K key)

（1）判断key是否为空，是的话，返回null key 所对应的值。

（2）如果不是，则返回key所对应的节点。

（3）判断节点是否为空，不为空则返回节点中的value值。

6、根据key获取节点：public final Entry<K,V> getEntry(Object key)

（1）获取key的hash值，利用for循环，通过indexFor，找到table的脚标index，轮询index所对应的所有节点e.next;

（2）判断每个节点的hash，key是否相等，相等才返回节点e。

HashMap的遍历方法：

1、采用keySet+for循环遍历：获取所有的key，再for循环获取value

Map<String,String> map=new HashMap<String,String>();

map.put("key1","value1");

map.put("key2","value2");

map.put("key3","value3");

for(String key:map.keySet()){

system.out.println("key:"+key);

system.out.println("value:"+map.get(key));

}

2、采用entrySet+for循环遍历；获取所有键值对，然后遍历

Set<Entry<String,String>> entries = map.entrySet();

for(Entry<String,String> entry: entries){

system.out.println("key:"+entry.getKey());

system.out.println("value:"+entry.getValue());

}

3、采用entrySet+iterator；用迭代器

Iterator< Map.Entry<String,String>> it=map.EntrySet().iterator();

while(it.hasNext()){

Map.Entry<String,String> entry=it.next();