Java基础十一-Map

• Map 中的数据是以键值对（key - value）的形式存储的
• key - value 以 Entry 类型的对象实例存在
• 可以通过 key 值快速的查找 value 值
• 一个映射不能包含重复的键
• 每个键最多只能映射到一个值
• 当访问的值不在的时候，方法会抛出一个 NoSuchElementException 异常
• 当对象的类型和 Map 里元素类型不兼容的时候，就会抛出一个 ClassCastException 异常
• 当在不允许使用 Null 对象的 Map 中使用Null对象，会抛出一个 NullPointerException 异常
• 当尝试修改一个只读的 Map 时，会抛出一个 UnsupportedOperationException 异常

常用的方法

• 添加或者修改功能
  • V put(K key, V value)：添加元素 /修改元素，并返回修改前元素的值
• 删除功能
  • void clear()：移除所有的键值对元素
  • V remove(Object key)：删除键对应的元素，并把值返回
• 判断功能
  • boolean containsKey(Object key)：判断集合是否包含指定的键
  • boolean containsValue(Object value)：判断集合是否包含指定的值
  • boolean isEmpty()：判断集合是否为空
• 获取功能
  • Set< Map.Entry< K,V>> entrySet()：遍历
  • V get(Object key)：根据键获取值
  • Set< K> keySet()：获取集合中所有键的集合
  • Collection< V> values()：获取集合中所有值的集合
• 长度功能
  • int size()：返回集合中的键值对的对数

HashMap

什么是Hash表

在讨论哈希表之前，我们先大概了解下其他数据结构在新增，查找等基础操作执行性能

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)

二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。

比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。

存储位置 = f(关键字)

其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。

哈希冲突

然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式

HashMap 是 Java 中 Map 的一个实现类，它是一个双列结构(数据+链表)，这样的结构使得它的查询和插入效率都很高。HashMap 允许 null 键和值，它的键唯一，元素的存储无序，并且它是线程不安全的。

由于 HashMap 的这些特性，它在 Java 中被广泛地使用，下面我们就基于 Java 8 分析一下 HashMap 的源码。

定义

HashMap 实现了 Map 接口，继承 AbstractMap。其中 Map 接口定义了键映射到值的规则，而 AbstractMap 类提供 Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作，其实 AbstractMap 类已经实现了 Map。

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

构造函数

HashMap提供了三个构造函数：

HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap

HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap

HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap

在这里提到了两个参数：初始容量，加载因子。这两个参数是影响 HashMap 性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是 O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

HashMap是一种支持快速存取的数据结构，要了解它的性能必须要了解它的数据结构。

数据结构

首先 HashMap 是一个双列结构，它是一个散列表，存储方式是键值对。 它继承了 AbstractMap，实现了 Map<K,V> Cloneable Serializable 接口。

HashMap 的双列结构是数组 Node[]+链表，我们知道数组的查询很快，但是修改很慢，因为数组定长，所以添加或者减少元素都会导致数组扩容。而链表结构恰恰相反，它的查询慢，因为没有索引，需要遍历链表查询。但是它的修改很快，不需要扩容，只需要在首或者尾部添加即可。HashMap 正是应用了这两种数据结构，以此来保证它的查询和修改都有很高的效率。

HashMap 在调用 put() 方法存储元素的时候，会根据 key 的 hash 值来计算它的索引，这个索引有什么用呢？HashMap 使用这个索引来将这个键值对储存到对应的数组位置，比如如果计算出来的索引是 n，则它将存储在 Node[n] 这个位置。

HashMap 在计算索引的时候尽量保证它的离散，但还是会有不同的 key 计算出来的索引是一样的，那么第二次 put 的时候，key 就会产生冲突。HashMap 用链表的结构解决这个问题，当 HashMap 发现当前的索引下已经有不为 null 的 Node 存在时，会在这个 Node 后面添加新元素，同一索引下的元素就组成了链表结构，Node 和 Node 之间如何联系可以看下面 Node 类的源码分析。

几个比较重要的字段

DEFAULT_INITIAL_CAPACITY，默认初始化的容量为16，必须是2的幂。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

MAXIMUM_CAPACITY，最大长度，2^30：

static final int MAXIMUM_CAPACITY = 1 << 30;

DEFAULT_LOAD_FACTOR，默认加载因子，0.75：

static final float DEFAULT_LOAD_FACTOR = 0.75f;

由链表转换成树的阈值TREEIFY_THRESHOLD

一个桶中 bin（箱子）的存储方式由链表转换成树的阈值。即当桶中bin的数量超过 TREEIFY_THRESHOLD 时使用树来代替链表。默认值是8

static final int TREEIFY_THRESHOLD = 8;

由树转换成链表的阈值UNTREEIFY_THRESHOLD

当执行resize操作时，当桶中bin的数量少于UNTREEIFY_THRESHOLD时使用链表来代替树。默认值是6

static final int UNTREEIFY_THRESHOLD = 6;

MIN_TREEIFY_CAPACITY

当桶中的 bin 被树化时最小的 hash 表容量。（如果没有达到这个阈值，即 hash 表容量小于MIN_TREEIFY_CAPACITY，当桶中 bin 的数量太多时会执行 resize 扩容操作）这个 MIN_TREEIFY_CAPACITY 的值至少是 TREEIFY_THRESHOLD 的4倍。

static final int MIN_TREEIFY_CAPACITY = 64;

Node

下边是非常重要的一个内部类 Node ，它实现了 Map.Entry，Node 是 HashMap 中的基本元素，每个键值对都储存在一个 Node 对象里， Node 类有四个成员变量：hash key 的哈希值、键值对 key 与 value，以及 next 指针。next 也是 Node 类型，这个 Node 指向的是链表下一个键值对，这也就是前文提到的 hash 冲突时 HashMap 的处理办法。

Node 类内部实现了 Map.Entry 接口中的 getKey()、getValue() 等方法，所以在遍历 Map 的时候我们可以用 Map.entrySet() 。

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

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

put() 流程

put() 方法

put() 主要是将 key 和 value 保存到 Node 数组中，HashMap 根据 key 的 hash 值来确定它的索引，源码里 put 方法将调用内部的 putVal() 方法。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

HashMap 在 put 键值对的时候会调用 hash() 方法计算 key 的 hash 值，hash() 方法会调用 Object 的 native 方法 hashCode() 并且将计算之后的 hash 值高低位做异或运算，以增加 hash 的复杂度。（Java 里一个 int 类型占 4 个字节，一个字节是 8 bit，所以下面源码中的 h 与 h 右移 16 位就相当于高低位异或）

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

putAll() 方法

这部分是主要 put 的逻辑

1. 计算容量：根据 map 的 size 计算数组容量大小，如果元素数量也就是 size 大于数组容量 ×0.75，则对数组进行扩容，扩容到原来的 2 倍。

2. 查找数据索引：根据 key 的 hash 值和数组长度找到 Node 数组索引。

3. 储存：这里有以下几种情况（假设计算出的 hash 为 i，数组为 tab，变量以代码为例）

   a. 当前索引为 null，直接 new 一个 Node 并存到数组里，tab[i]=newNode(hash, key, value, null)

   b. 数组不为空，这时两个元素的 hash 是一样的，再调用 equals 方法判断 key 是否一致，相同，则覆盖当前的 value，否则继续向下判断

   c. 上面两个条件都不满足，说明 hash 发生冲突，Java 8 里实现了红黑树，红黑树在进行插入和删除操作时通过特定算法保持二叉查找树的平衡，从而可以获得较高的查找性能。本篇也是基于 Java 8 的源码进行分析，在这里 HashMap 会判断当前数组上的元素 tab[i] 是否是红黑树，如果是，调用红黑树的 putTreeVal 的 put 方法，它会将新元素以红黑树的数据结构储存到数组中。

如果以上条件都不成立，表明 tab[i] 上有其它 key 元素存在，并且没有转成红黑树结构，这时只需调用 tab[i].next 来遍历此链表，找到链表的尾然后将元素存到当前链表的尾部。

transient Node<K,V>[] table;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
            boolean evict) {
 Node<K,V>[] tab; Node<K,V> p; int n, i;
 // 根据当前的map size计算容量大小capacity， 主要实现是在resize()中计算capacity，需要扩容的时候， 长度左移一位（二倍）
 if ((tab = table) == null || (n = tab.length) == 0)
     n = (tab = resize()).length;
 // 这里就是经常说的桶结构了， 看过HashMap介绍的都知道它的内部有不同的桶, 这个桶实际上就是一个链表结构
 // 在这个地方， HashMap先判断key所属的桶是否存在。 (n - 1) & hash 相当于计算桶的序号， 根据桶序号来找到对应的桶
 // 这里的table 是HashMap的数组， 数组为空就新建一个数组 newNode(hash, key, value, null)
 if ((p = tab[i = (n - 1) & hash]) == null)
     tab[i] = newNode(hash, key, value, null);
 else {
     //数组不为空， 先判断key是否存在， 存在 就覆盖value
     Node<K,V> e; K k;
     if (p.hash == hash &&
         ((k = p.key) == key || (key != null && key.equals(k))))
         e = p;
     // 如果此链表是红黑树结构（TreeNode）
     else if (p instanceof TreeNode)
         e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
     else {
         // 循环当前链表， 找出p.next为空的位置就是链表的末端， 添加上
         for (int binCount = 0; ; ++binCount) {
             if ((e = p.next) == null) { 
                p.next = newNode(hash, key, value, null);
                 // 这里会判断这个链表是否需要转换为红黑树链表
                 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                     treeifyBin(tab, hash);
                 break;
             }
             if (e.hash == hash &&
                 ((k = e.key) == key || (key != null && key.equals(k))))
                 break;
             p = e;
         }
     }
     if (e != null) { // existing mapping for key
         V oldValue = e.value;
         if (!onlyIfAbsent || oldValue == null)
             e.value = value;
         afterNodeAccess(e);
         return oldValue;
     }
 }
 ++modCount;
 if (++size > threshold)
     // put之后，如果元素个数大于当前的数组容量了，进行数组扩容
     resize();
 afterNodeInsertion(evict);
 return null;
}

get()

get() 方法

get() 方法会调用 getNode() 方法，这是 get() 的核心，getNode() 方法的两个参数分别是 hash 值和 key。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

这里重点来看 getNode() 方法，前面讲到过，HashMap 是通过 key 生成的 hash 值来存储到数组的对应索引上，HashMap 在 get 的时候也是用这种方式来查找元素的。

1. 根据 hash 值和数组长度找到 key 对应的数组索引。
2. 拿到当前的数组元素，也就是这个链表的第一个元素 first，先用 hash 和 equals() 判断是不是第一个元素，是的话直接返回，不是的话继续下面的逻辑。
3. 不是链表的第一个元素，判断这个元素 first 是不是红黑树，如果是调用红黑树的 getTreeNode 方法来查询。
4. 如果不是红黑树结构，从 first 元素开始遍历当前链表，直到找到要查询的元素，如果没有则返回 null。

final Node<K,V> getNode(int hash, Object key) {
  	// tab： HashMap的数组
    Node<K,V>[] tab; 
  	Node<K,V> first, e;
  	int n; K k;
    // 判断数组不为空， 桶不为空
  	if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
      	// 先查询桶的第一个元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
      	// 不是第一个元素
        if ((e = first.next) != null) {
          	// 如果是红黑树， 则用红黑树的方法查询
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
          	// 不是红黑树， 遍历桶， 直到找到对应的key， 返回
            do {
              	 // 1. 判断hash值是否相等； 
              	 // 2. 判断key相等。 防止hash碰撞发生
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

HashMap 的扩容机制

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。

我们分析下resize的源码，鉴于JDK1.8融入了红黑树，较复杂，为了便于理解我们仍然使用JDK1.7的代码，好理解一些，本质上区别不大，具体区别后文再说。

void resize(int newCapacity) {   //传入新的容量
  Entry[] oldTable = table;    //引用扩容前的Entry数组
  int oldCapacity = oldTable.length;
  if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
    threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
    return;
  }
  Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
  transfer(newTable);                         //！！将数据转移到新的Entry数组里
  table = newTable;                           //HashMap的table属性引用新的Entry数组
  threshold = (int)(newCapacity * loadFactor);//修改阈值
}

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

void transfer(Entry[] newTable) {
  Entry[] src = table;                   //src引用了旧的Entry数组
  int newCapacity = newTable.length;
  for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
    Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
    if (e != null) {
      src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
      do {
        Entry<K,V> next = e.next;
        int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
        e.next = newTable[i]; //标记[1]
        newTable[i] = e;      //将元素放在数组上
        e = next;             //访问下一个Entry链上的元素
      }while (e != null);
    }
  }
}

newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话），这一点和Jdk1.8有区别，下文详解。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程。

下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码，写的很赞，如下:

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
       // 超过最大值就不再扩充了，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
       // 没超过最大值，就扩充为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
  	// 计算新的resize上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
      	// 把每个bucket都移动到新的buckets中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order // 链表优化重hash的代码块
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                      	// 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                      	// 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                  	// 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                  	// 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

LinkedHashMap

​ LinkedHashMap继承自HashMap，是Hash表和链表的实现，并且依靠着双向链表保证了迭代顺序是插入的顺序。如果 一个key重新插入到LinkedHashMap中，那么这个插入顺序是无效的，也就是说，如果m.put(K,V)时，调用m.containsKey(k),将会返回true，更新value值，但是顺序不变。

public class TestLinkHashMap {
    public static  void main(String[] args){
        Map<String,Object> map = new LinkedHashMap<>();
        map.put("1","1");
        map.put("2","2");
        map.put("3","3");
        //重新插入"1"
        map.put("1","4");

        for (Map.Entry<String,Object> entry:map.entrySet()) {
            System.out.println("key="+entry.getKey()+" "+"value="+entry.getValue());
        }
    }
}

运行结果

key=1 value=4
key=2 value=2
key=3 value=3

从上面的程序我们可以看见，同一key的多次插入，并不会影响其顺序

数据结构

循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点，迭代器遍历方向是从链表的头部开始到链表尾部结束，在链表尾部有一个空的header节点，该节点不存放key-value内容，为LinkedHashMap类的成员属性，循环双向链表的入口；

它继承了HashMap的Node，Node基础上添加了before和after两个指针，

static class Entry<K,V> extends HashMap.Node<K,V> {
  Entry<K,V> before, after;
  Entry(int hash, K key, V value, Node<K,V> next) {
    super(hash, key, value, next);
  }
}

重要的属性

/**
  * 双向链表的头部(eldest)
  */
 transient LinkedHashMap.Entry<K,V> head;

 /**
  * 双向链表的尾部(youngest)
  */
 transient LinkedHashMap.Entry<K,V> tail;

 /**
  * 
  *accessOrder为true时，按访问顺序排序，false时，按插入顺序排序
  * 
  */
 final boolean accessOrder;

重点的方法

1. LinkedHashMap的Entry是继承与Node类，也就是LinkedHashMap与HashMap的根本区别所在，Node是链表形式，只有next与下一个元素进行连接，而Entry的链表有before和after两个连接点。

   static class Entry<K,V> extends HashMap.Node<K,V> {
     Entry<K,V> before, after;
     Entry(int hash, K key, V value, Node<K,V> next) {
       super(hash, key, value, next);
     }
   }

   区别是将节点变成Entry，并且按照链表方式将元素有序连接

   Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
     LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
     linkNodeLast(p);
     return p;
   }

2. afterNodeAccess方法

   void afterNodeAccess(Node<K,V> e) { // move node to last
     LinkedHashMap.Entry<K,V> last;
     // 若访问顺序为true，且访问的对象不是尾结点
     if (accessOrder && (last = tail) != e) {
       // 向下转型，记录p的前后结点
       LinkedHashMap.Entry<K,V> p =
         (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
       // p的后结点为空
       p.after = null;
       // 如果p的前结点为空
       if (b == null)
         // a为头结点
         head = a;
       else // p的前结点不为空
         // b的后结点为a
         b.after = a;
       // p的后结点不为空
       if (a != null)
         // a的前结点为b
         a.before = b;
       else // p的后结点为空
         // 后结点为最后一个结点
         last = b;
       // 若最后一个结点为空
       if (last == null)
         // 头结点为p
         head = p;
       else { // p链入最后一个结点后面
         p.before = last;
         last.after = p;
       }
       // 尾结点为p
       tail = p;
       // 增加结构性修改数量
       ++modCount;
     }
   }

   就是说在进行put之后就算是对节点的访问了，那么这个时候就会更新链表，把最近访问的放到最后，保证链表。关键参数是accessOrder，这个参数只有在public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) 中可以手动设置为true，其余时候都默认为false

HashTable

概述

HashTable和HashMap两种集合非常相似，经常被各种面试官问到两者的区别。

1. HashMap是非同步的，没有对读写等操作进行锁保护，所以是线程不安全的，在多线程场景下会出现数据不一致的问题。而HashTable是同步的，所有的读写等操作都进行了锁（synchronized）保护，在多线程环境下没有安全问题。但是锁保护也是有代价的，会对读写的效率产生较大影响。

2. HashMap结构中，是允许保存null的，Entry.key和Entry.value均可以为null。但是HashTable中是不允许保存null的。

3. HashMap的迭代器（Iterator）是fail-fast迭代器，但是Hashtable的迭代器（enumerator）不是fail-fast的。如果有其它线程对HashMap进行的添加/删除元素，将会抛出ConcurrentModificationException，但迭代器本身的remove方法移除元素则不会抛出异常。这条同样也是Enumeration和Iterator的区别。

原理

HashTable类中，保存实际数据的，依然是Entry对象。其数据结构与HashMap是相同的。
HashTable类继承自Dictionary类，实现了三个接口，分别是Map，Cloneable和java.io.Serializable，如下图所示。

HashTable中的主要方法，如put，get，remove和rehash等，与HashMap中的功能相同

源码分析

put()方法

put方法的主要逻辑如下：

1. 先获取synchronized锁。
2. put方法不允许null值，如果发现是null，则直接抛出异常。
3. 计算key的哈希值和index
4. 遍历对应位置的链表，如果发现已经存在相同的hash和key，则更新value，并返回旧值。
5. 如果不存在相同的key的Entry节点，则调用addEntry方法增加节点。
6. addEntry方法中，如果需要则进行扩容，之后添加新节点到链表头部。

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

get()方法

get方法的主要逻辑如下

1. 先获取synchronized锁。
2. 计算key的哈希值和index。
3. 在对应位置的链表中寻找具有相同hash和key的节点，返回节点的value。
4. 如果遍历结束都没有找到节点，则返回null。

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

rehash扩容方法

rehash扩容方法主要逻辑如下：

1. 数组长度增加一倍（如果超过上限，则设置成上限值）。
2. 更新哈希表的扩容门限值。
3. 遍历旧表中的节点，计算在新表中的index，插入到对应位置链表的头部。

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

remove()方法

remove方法主要逻辑如下：

1. 先获取synchronized锁。
2. 计算key的哈希值和index。
3. 遍历对应位置的链表，寻找待删除节点，如果存在，用e表示待删除节点，pre表示前驱节点。如果不存在，返回null。
4. 更新前驱节点的next，指向e的next。返回待删除节点的value值。

小结

HashTable相对于HashMap的最大特点就是线程安全，所有的操作都是被synchronized锁保护的

TreeMap

https://www.jianshu.com/p/69f11fc9ea38

https://www.cnblogs.com/Java3y/p/8808818.html