HashMap存储结构

• HashMap采用数组+链表这种存储结构（为解决链表过长导致的遍历效率低，jdk1.8之后采用数组+链表+红黑树这种结构），我们知道数组这种结构，查询遍历快，但增删操作慢，而链表增删快，查询慢。于是HashMap结合二者的优势，具体是这样的（这里涉及到HashMap的存储结构）：

1. 数组你不是查询快吗，那我的哈希表就采用数组结构，即通过hash算法生成的哈希值即为哈希表中的存储位置。
2. 链表你不是插入快吗，那我就存entry的时候利用链表插入，并解决了hash冲突的问题。

• HashMap的桶式结构

  
  数组+链表

这里说明一下，前面数组是hash表，存放每一个链表的头指针；后面是链表结构。

HashMap用法

public static void main(String[] args) {
HashMap<Integer,String > map=new HashMap<>();
map.put(1, "张士超");
map.put(1, "张士超2");
map.put(4, "张士超4");
map.put(6, "张士超6");
System.out.println(map.get(1));
System.out.println(map.get(2));
System.out.println(map.keySet());
Iterator iterator=map.keySet().iterator();
while(iterator.hasNext()) {
    int key=(Integer)iterator.next();
    System.out.println(map.get(key));
}
}

HashMap的构造方法

HashMap有四种构造方法：

HashMap():构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空HashMap;
HashMap(int initialCapacity) :构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor): 构造一个带指定初始容量和加载因子的空 HashMap。
HashMap(Map<? extends K,? extends V> m):构造一个映射关系与指定 Map 相同的新 HashMap。

• HashMap有两个关键参数：初始容量和加载因子，初始容量：哈希表的数组长度,默认为16；加载因子：表示当前已用的数组空间与初始容量的比值如果大于大于这个加载因子，表示数组容量不够了，此时需要数组扩容，对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

HashMap存数据（put方法）

想要用HashMap存数据，要解决两个问题:

1. 存在哪个位置；
2. hash冲突怎么解决。

• 存在哪个位置呢，看源码

 int hash = hash(key);
 int i = indexFor(hash, table.length);

即通过当前的key生成hash值作为哈希表的数组存储位置，这里涉及到一个hash算法的问题，简单来说就是通过一系列的&、||、^和一些取余、取模运算，尽量使得计算的结果没有规律性可循。

• hash冲突怎么办呢，实际存储数据用链表，hash表里只存链表的头指针。举个栗子，假设我先存一个entry<"1","1">,放在hash表数组0的位置，然后我再存一个entry<"2","2">，假设也是0的位置，这样会以这种形式存储：

entry<"2","2">——>entry<"1","1">

这里说明一下，假设现在我又存一个数据entry<"1","2">，这个数据会不会直接插在表头呢，不会的，他会更新之前的entry<"1","1">数据，具体是比较key的hash()和equal()方法，如果都相等，证明是一个entry，此时变成了：

entry<"2","2">——>entry<"1","2">

hashmap取数据（get方法）

• hashmap.get(key)方法可以取得entry的“value”值，具体是怎么做的呢，看源码：

int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> 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;
}

• 这个取值就很简单了，首先通过hash（key）获取散列表（哈希表）中的数组位置，确定该entry去哪个链表里面查找；然后遍历整个链表就可以了,遍历的时候判断key的hash()和equal()方法是否相等，找到那个key对应的value即可。
• 这里说明一下：
  1.key的对应的object一定要重写hashcode()和equal()方法，不然会存在找不到或者找错的问题

2. 我们之前说过的，链表查询速度慢，所以链表长度的默认阈值为8，当长度超过8时，则会采用红黑树的结构来提高遍历效率（jdk1.8以上），结构如下：

   
   数组+链表+红黑树

HashMap多线程问题

1.由于HashMap不是线程安全的，所以多线程的put存数据肯定会存在问题，可能造成存错、存空等问题。
2.多线程造成循环列表、导致get死循环，简单来说，就是两个线程那个同时对hash表进行扩容处理（rehash处理），导致链表很容易产生回路，然后在get操作时产生死循环！

多线程造成的链表死循环.png

3. 改进方法就是在多线程中用ConcurrentHashMap或者HashTable代替HashMap。

HashMap与LinkedHashMap的区别与联系

1. LinkedHashMap是HashMap的子类，HashMap有的方法LinkedHashMap都有，都是数组+链表的存储结构，但与HashMap不同的是，链表双向循环链表，它可以做到有序。
2. 因为双向循环链表的存在，LinkedHashMap可以记录数据插入的顺序。

创作不易，交出你的小心心！！！！！！！！！！！！！！！！！