问题导读：
    1、LinkedList的定义是什么？
    2、LinkedList元素的处理方法有哪些？
    3、HashMap底层数据结构是什么样？
    4、HashMap方法都有哪些？

    Java高级特性增强-集合框架(LinkedList/HashMap)**

    本部分网络上有大量的资源可以参考，在这里做了部分整理，感谢前辈的付出，每节文章末尾有引用列表，源码推荐看JDK1.8以后的版本，注意甄别~ ####多线程 ###集合框架 ###NIO ###Java并发容器

    集合框架

    Java中的集合框架

    ArrayList/Vector LinkedList HashMap HashSet LinkedHashMap … 本章内容参考引用网上的内容为主，网上有大量优质的资源，作者在这里做了整理如下：

    LinkedList（基于JDK1.8）LinkedList 定义
    LinkedList 是一个用链表实现的集合，元素有序且可以重复。

    1. public class LinkedList<E>
    2.      extends AbstractSequentialList<E>
    3.      implements List<E>, Deque<E>, Cloneable, java.io.Serializable

    image.png
    和 ArrayList 集合一样，LinkedList 集合也实现了Cloneable接口和Serializable接口，分别用来支持克隆以及支持序列化。List 接口也不用多说，定义了一套 List 集合类型的方法规范。注意，相对于 ArrayList 集合，LinkedList 集合多实现了一个 Deque 接口，这是一个双向队列接口，双向队列就是两端都可以进行增加和删除操作。

    字段属性

    1. //链表元素（节点）的个数
    2.     transient int size = 0;
    4.     /**
    5.      *指向第一个节点的指针
    6.      */
    7.     transient Node<E> first;
    9.     /**
    10.      *指向最后一个节点的指针
    11.      */
    12.     transient Node<E> last;

    注意这里出现了一个 Node 类，这是 LinkedList 类中的一个内部类，其中每一个元素就代表一个 Node 类对象，LinkedList 集合就是由许多个 Node 对象类似于手拉着手构成。

    1. private static class Node<E> {
    2.         E item;//实际存储的元素
    3.         Node<E> next;//指向上一个节点的引用
    4.         Node<E> prev;//指向下一个节点的引用
    6.         //构造函数
    7.         Node(Node<E> prev, E element, Node<E> next) {
    8.             this.item = element;
    9.             this.next = next;
    10.             this.prev = prev;
    11.         }
    12.     }

    如下图所示：
    image.png

    上图的 LinkedList 是有四个元素，也就是由 4 个 Node 对象组成，size=4，head 指向第一个elementA,tail指向最后一个节点elementD。

    构造函数

    1. public LinkedList() {
    2.     }
    3.     public LinkedList(Collection<? extends E> c) {
    4.         this();
    5.         addAll(c);
    6.     }

    LinkedList 有两个构造函数，第一个是默认的空的构造函数，第二个是将已有元素的集合Collection 的实例添加到 LinkedList 中，调用的是 addAll() 方法，这个方法下面我们会介绍。 　　注意：LinkedList 是没有初始化链表大小的构造函数，因为链表不像数组，一个定义好的数组是必须要有确定的大小，然后去分配内存空间，而链表不一样，它没有确定的大小，通过指针的移动来指向下一个内存地址的分配。

    添加元素

    addFirst(E e) 将指定元素添加到链表头

    1. //将指定的元素附加到链表头节点
    2.     public void addFirst(E e) {
    3.         linkFirst(e);
    4.     }
    5.     private void linkFirst(E e) {
    6.         final Node<E> f = first;//将头节点赋值给 f
    7.         final Node<E> newNode = new Node<>(null, e, f);//将指定元素构造成一个新节点，此节点的指向下一个节点的引用为头节点
    8.         first = newNode;//将新节点设为头节点，那么原先的头节点 f 变为第二个节点
    9.         if (f == null)//如果第二个节点为空，也就是原先链表是空
    10.             last = newNode;//将这个新节点也设为尾节点（前面已经设为头节点了）
    11.         else
    12.             f.prev = newNode;//将原先的头节点的上一个节点指向新节点
    13.         size++;//节点数加1
    14.         modCount++;//和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
    15.     }

    addLast(E e)和add(E e) 将指定元素添加到链表尾

    1. //将元素添加到链表末尾
    2.     public void addLast(E e) {
    3.         linkLast(e);
    4.     }
    5.     //将元素添加到链表末尾
    6.     public boolean add(E e) {
    7.         linkLast(e);
    8.         return true;
    9.     }
    10.     void linkLast(E e) {
    11.         final Node<E> l = last;//将l设为尾节点
    12.         final Node<E> newNode = new Node<>(l, e, null);//构造一个新节点，节点上一个节点引用指向尾节点l
    13.         last = newNode;//将尾节点设为创建的新节点
    14.         if (l == null)//如果尾节点为空，表示原先链表为空
    15.             first = newNode;//将头节点设为新创建的节点（尾节点也是新创建的节点）
    16.         else
    17.             l.next = newNode;//将原来尾节点下一个节点的引用指向新节点
    18.         size++;//节点数加1
    19.         modCount++;//和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
    20.     }

    addAll(Collection<? extends E> c) 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾

    　　此方法还有一个 addAll(int index, Collection<? extends E> c)，将集合 c 中所有元素插入到指定索引的位置。其实 addAll(Collection<? extends E> c) == addAll(size, Collection<? extends E> c)

    删除元素

    删除元素和添加元素一样，也是通过更改指向上一个节点和指向下一个节点的引用即可. remove()和removeFirst() 　　从此列表中移除并返回第一个元素 removeLast() 　　从该列表中删除并返回最后一个元素 remove(int index) 　　删除此列表中指定位置的元素 remove(Object o) 如果存在，则从该列表中删除指定元素的第一次出现 　　此方法本质上和 remove(int index) 没多大区别，通过循环判断元素进行删除，需要注意的是，是删除第一次出现的元素，不是所有的。

    修改元素

    通过调用 set(int index, E element) 方法，用指定的元素替换此列表中指定位置的元素。

    1. public E set(int index, E element) {
    2.         //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常
    3.         checkElementIndex(index);
    4.         Node<E> x = node(index);//获取指定索引处的元素
    5.         E oldVal = x.item;
    6.         x.item = element;//将指定位置的元素替换成要修改的元素
    7.         return oldVal;//返回指定索引位置原来的元素
    8.     }

    这里主要是通过 node(index) 方法获取指定索引位置的节点，然后修改此节点位置的元素即可。

    查找元素

    getFirst() 　　返回此列表中的第一个元素 getLast() 　　返回此列表中的最后一个元素 get(int index) 　　返回指定索引处的元素 indexOf(Object o) 　　返回此列表中指定元素第一次出现的索引，如果此列表不包含元素，则返回-1。

    遍历集合

    普通for循环

    1. LinkedList<String> linkedList = new LinkedList<>();
    2. linkedList.add("A");
    3. linkedList.add("B");
    4. linkedList.add("C");
    5. linkedList.add("D");
    6. for(int i = 0 ; i < linkedList.size() ; i++){
    7.     System.out.print(linkedList.get(i)+" ");//A B C D
    8. }

    代码很简单，我们就利用 LinkedList 的 get(int index) 方法，遍历出所有的元素。 　　但是需要注意的是， get(int index) 方法每次都要遍历该索引之前的所有元素，这句话这么理解： 　　比如上面的一个 LinkedList 集合，我放入了 A,B,C,D是个元素。总共需要四次遍历： 　　第一次遍历打印 A：只需遍历一次。 　　第二次遍历打印 B：需要先找到 A，然后再找到 B 打印。 　　第三次遍历打印 C：需要先找到 A，然后找到 B，最后找到 C 打印。 　　第四次遍历打印 D：需要先找到 A，然后找到 B，然后找到 C，最后找到 D。 　　这样如果集合元素很多，越查找到后面（当然此处的get方法进行了优化，查找前半部分从前面开始遍历，查找后半部分从后面开始遍历，但是需要的时间还是很多）花费的时间越多。那么如何改进呢？

    迭代器
    **

    1. LinkedList<String> linkedList = new LinkedList<>();
    2. linkedList.add("A");
    3. linkedList.add("B");
    4. linkedList.add("C");
    5. linkedList.add("D");
    8. Iterator<String> listIt = linkedList.listIterator();
    9. while(listIt.hasNext()){
    10.     System.out.print(listIt.next()+" ");//A B C D
    11. }
    13. //通过适配器模式实现的接口，作用是倒叙打印链表
    14. Iterator<String> it = linkedList.descendingIterator();
    15. while(it.hasNext()){
    16.     System.out.print(it.next()+" ");//D C B A
    17. }

    在 LinkedList 集合中也有一个内部类 ListItr，方法实现大体上也差不多，通过移动游标指向每一次要遍历的元素，不用在遍历某个元素之前都要从头开始。其方法实现也比较简单：

    1. public ListIterator<E> listIterator(int index) {
    2.         checkPositionIndex(index);
    3.         return new ListItr(index);
    4.     }
    6.     private class ListItr implements ListIterator<E> {
    7.         private Node<E> lastReturned;
    8.         private Node<E> next;
    9.         private int nextIndex;
    10.         private int expectedModCount = modCount;
    12.         ListItr(int index) {
    13.             // assert isPositionIndex(index);
    14.             next = (index == size) ? null : node(index);
    15.             nextIndex = index;
    16.         }
    18.         public boolean hasNext() {
    19.             return nextIndex < size;
    20.         }
    22.         public E next() {
    23.             checkForComodification();
    24.             if (!hasNext())
    25.                 throw new NoSuchElementException();
    27.             lastReturned = next;
    28.             next = next.next;
    29.             nextIndex++;
    30.             return lastReturned.item;
    31.         }
    33.         public boolean hasPrevious() {
    34.             return nextIndex > 0;
    35.         }
    37.         public E previous() {
    38.             checkForComodification();
    39.             if (!hasPrevious())
    40.                 throw new NoSuchElementException();
    42.             lastReturned = next = (next == null) ? last : next.prev;
    43.             nextIndex--;
    44.             return lastReturned.item;
    45.         }
    47.         public int nextIndex() {
    48.             return nextIndex;
    49.         }
    51.         public int previousIndex() {
    52.             return nextIndex - 1;
    53.         }
    55.         public void remove() {
    56.             checkForComodification();
    57.             if (lastReturned == null)
    58.                 throw new IllegalStateException();
    60.             Node<E> lastNext = lastReturned.next;
    61.             unlink(lastReturned);
    62.             if (next == lastReturned)
    63.                 next = lastNext;
    64.             else
    65.                 nextIndex--;
    66.             lastReturned = null;
    67.             expectedModCount++;
    68.         }
    70.         public void set(E e) {
    71.             if (lastReturned == null)
    72.                 throw new IllegalStateException();
    73.             checkForComodification();
    74.             lastReturned.item = e;
    75.         }
    77.         public void add(E e) {
    78.             checkForComodification();
    79.             lastReturned = null;
    80.             if (next == null)
    81.                 linkLast(e);
    82.             else
    83.                 linkBefore(e, next);
    84.             nextIndex++;
    85.             expectedModCount++;
    86.         }
    88.         public void forEachRemaining(Consumer<? super E> action) {
    89.             Objects.requireNonNull(action);
    90.             while (modCount == expectedModCount && nextIndex < size) {
    91.                 action.accept(next.item);
    92.                 lastReturned = next;
    93.                 next = next.next;
    94.                 nextIndex++;
    95.             }
    96.             checkForComodification();
    97.         }
    99.         final void checkForComodification() {
    100.             if (modCount != expectedModCount)
    101.                 throw new ConcurrentModificationException();
    102.         }
    103.     }

    这里需要重点注意的是 modCount 字段，前面我们在增加和删除元素的时候，都会进行自增操作 modCount，这是因为如果想一边迭代，一边用集合自带的方法进行删除或者新增操作，都会抛出异常。（使用迭代器的增删方法不会抛异常）

    1. final void checkForComodification() {
    2.             if (modCount != expectedModCount)
    3.                 throw new ConcurrentModificationException();
    4.         }

    比如：

    1. LinkedList<String> linkedList = new LinkedList<>();
    2. linkedList.add("A");
    3. linkedList.add("B");
    4. linkedList.add("C");
    5. linkedList.add("D");
    8. Iterator<String> listIt = linkedList.listIterator();
    9. while(listIt.hasNext()){
    10.     System.out.print(listIt.next()+" ");//A B C D
    11.     //linkedList.remove();//此处会抛出异常
    12.     listIt.remove();//这样可以进行删除操作
    13. }

    迭代器的另一种形式就是使用 foreach 循环，底层实现也是使用的迭代器.

    1. LinkedList<String> linkedList = new LinkedList<>();
    2. linkedList.add("A");
    3. linkedList.add("B");
    4. linkedList.add("C");
    5. linkedList.add("D");
    6. for(String str : linkedList){
    7.     System.out.print(str + "");
    8. }

    HashMap（基于JDK1.8）

    HashMap简介

    HashMap 主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。 JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

    底层数据结构分析

    JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。 所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。 JDK 1.8 HashMap 的 hash 方法源码: JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

    1. static final int hash(Object key) {
    2.       int h;
    3.       // key.hashCode()：返回散列值也就是hashcode
    4.       // ^ ：按位异或
    5.       // >>>:无符号右移，忽略符号位，空位都以0补齐
    6.       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    7.   }

    对比一下 JDK1.7的 HashMap 的 hash 方法源码.

    1. static int hash(int h) {
    2.     // This function ensures that hashCodes that differ only by
    3.     // constant multiples at each bit position have a bounded
    4.     // number of collisions (approximately 8 at default load factor).
    6.     h ^= (h >>> 20) ^ (h >>> 12);
    7.     return h ^ (h >>> 7) ^ (h >>> 4);
    8. }

    相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

    所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
    image.png
    JDK1.8之后 相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
    image.png
    类的属性：

    1. public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    2.     // 序列号
    3.     private static final long serialVersionUID = 362498820763181265L;    
    4.     // 默认的初始容量是16
    5.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    6.     // 最大容量
    7.     static final int MAXIMUM_CAPACITY = 1 << 30; 
    8.     // 默认的填充因子
    9.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
    10.     // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    11.     static final int TREEIFY_THRESHOLD = 8; 
    12.     // 当桶(bucket)上的结点数小于这个值时树转链表
    13.     static final int UNTREEIFY_THRESHOLD = 6;
    14.     // 桶中结构转化为红黑树对应的table的最小大小
    15.     static final int MIN_TREEIFY_CAPACITY = 64;
    16.     // 存储元素的数组，总是2的幂次倍
    17.     transient Node<k,v>[] table; 
    18.     // 存放具体元素的集
    19.     transient Set<map.entry<k,v>> entrySet;
    20.     // 存放元素的个数，注意这个不等于数组的长度。
    21.     transient int size;
    22.     // 每次扩容和更改map结构的计数器
    23.     transient int modCount;   
    24.     // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    25.     int threshold;
    26.     // 填充因子
    27.     final float loadFactor;
    28. }

    loadFactor加载因子
    loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，load Factor越小，也就是趋近于0，

    loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。

    给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

    threshold

    threshold = capacity * loadFactor，当Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。

    Node节点类源码:

    1. // 继承自 Map.Entry<K,V>
    2. static class Node<K,V> implements Map.Entry<K,V> {
    3.        final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
    4.        final K key;//键
    5.        V value;//值
    6.        // 指向下一个节点
    7.        Node<K,V> next;
    8.        Node(int hash, K key, V value, Node<K,V> next) {
    9.             this.hash = hash;
    10.             this.key = key;
    11.             this.value = value;
    12.             this.next = next;
    13.         }
    14.         public final K getKey()        { return key; }
    15.         public final V getValue()      { return value; }
    16.         public final String toString() { return key + "=" + value; }
    17.         // 重写hashCode()方法
    18.         public final int hashCode() {
    19.             return Objects.hashCode(key) ^ Objects.hashCode(value);
    20.         }
    22.         public final V setValue(V newValue) {
    23.             V oldValue = value;
    24.             value = newValue;
    25.             return oldValue;
    26.         }
    27.         // 重写 equals() 方法
    28.         public final boolean equals(Object o) {
    29.             if (o == this)
    30.                 return true;
    31.             if (o instanceof Map.Entry) {
    32.                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    33.                 if (Objects.equals(key, e.getKey()) &&
    34.                     Objects.equals(value, e.getValue()))
    35.                     return true;
    36.             }
    37.             return false;
    38.         }
    39. }

    树节点类源码:

    1. static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    2.         TreeNode<K,V> parent;  // 父
    3.         TreeNode<K,V> left;    // 左
    4.         TreeNode<K,V> right;   // 右
    5.         TreeNode<K,V> prev;    // needed to unlink next upon deletion
    6.         boolean red;           // 判断颜色
    7.         TreeNode(int hash, K key, V val, Node<K,V> next) {
    8.             super(hash, key, val, next);
    9.         }
    10.         // 返回根节点
    11.         final TreeNode<K,V> root() {
    12.             for (TreeNode<K,V> r = this, p;;) {
    13.                 if ((p = r.parent) == null)
    14.                     return r;
    15.                 r = p;
    16.        }

    HashMap源码分析

    构造方法
    image.png

    1. // 默认构造函数。
    2.     public More ...HashMap() {
    3.         this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
    4.      }
    6.      // 包含另一个“Map”的构造函数
    7.      public More ...HashMap(Map<? extends K, ? extends V> m) {
    8.          this.loadFactor = DEFAULT_LOAD_FACTOR;
    9.          putMapEntries(m, false);//下面会分析到这个方法
    10.      }
    12.      // 指定“容量大小”的构造函数
    13.      public More ...HashMap(int initialCapacity) {
    14.          this(initialCapacity, DEFAULT_LOAD_FACTOR);
    15.      }
    17.      // 指定“容量大小”和“加载因子”的构造函数
    18.      public More ...HashMap(int initialCapacity, float loadFactor) {
    19.          if (initialCapacity < 0)
    20.              throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    21.          if (initialCapacity > MAXIMUM_CAPACITY)
    22.              initialCapacity = MAXIMUM_CAPACITY;
    23.          if (loadFactor <= 0 || Float.isNaN(loadFactor))
    24.              throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    25.          this.loadFactor = loadFactor;
    26.          this.threshold = tableSizeFor(initialCapacity);
    27.      }

    putMapEntries方法：

    1. final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    2.     int s = m.size();
    3.     if (s > 0) {
    4.         // 判断table是否已经初始化
    5.         if (table == null) { // pre-size
    6.             // 未初始化，s为m的实际元素个数
    7.             float ft = ((float)s / loadFactor) + 1.0F;
    8.             int t = ((ft < (float)MAXIMUM_CAPACITY) ?
    9.                     (int)ft : MAXIMUM_CAPACITY);
    10.             // 计算得到的t大于阈值，则初始化阈值
    11.             if (t > threshold)
    12.                 threshold = tableSizeFor(t);
    13.         }
    14.         // 已初始化，并且m元素个数大于阈值，进行扩容处理
    15.         else if (s > threshold)
    16.             resize();
    17.         // 将m中的所有元素添加至HashMap中
    18.         for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
    19.             K key = e.getKey();
    20.             V value = e.getValue();
    21.             putVal(hash(key), key, value, false, evict);
    22.         }
    23.     }
    24. }

    put方法 HashMap只提供了put用于添加元素，putVal方法只是给put方法调用的一个方法，并没有提供给用户使用。

    对putVal方法添加元素的分析如下：

    ①如果定位到的数组位置没有元素 就直接插入。 ②如果定位到的数组位置有元素就和要插入的key比较，如果key相同就直接覆盖，如果key不相同，就判断p是否是一个树节点，如果是就调用e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入。

    image.png

    1. public V put(K key, V value) {
    2.     return putVal(hash(key), key, value, false, true);
    3. }
    5. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    6.                    boolean evict) {
    7.     Node<K,V>[] tab; Node<K,V> p; int n, i;
    8.     // table未初始化或者长度为0，进行扩容
    9.     if ((tab = table) == null || (n = tab.length) == 0)
    10.         n = (tab = resize()).length;
    11.     // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    12.     if ((p = tab[i = (n - 1) & hash]) == null)
    13.         tab = newNode(hash, key, value, null);
    14.     // 桶中已经存在元素
    15.     else {
    16.         Node<K,V> e; K k;
    17.         // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
    18.         if (p.hash == hash &&
    19.             ((k = p.key) == key || (key != null && key.equals(k))))
    20.                 // 将第一个元素赋值给e，用e来记录
    21.                 e = p;
    22.         // hash值不相等，即key不相等；为红黑树结点
    23.         else if (p instanceof TreeNode)
    24.             // 放入树中
    25.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    26.         // 为链表结点
    27.         else {
    28.             // 在链表最末插入结点
    29.             for (int binCount = 0; ; ++binCount) {
    30.                 // 到达链表的尾部
    31.                 if ((e = p.next) == null) {
    32.                     // 在尾部插入新结点
    33.                     p.next = newNode(hash, key, value, null);
    34.                     // 结点数量达到阈值，转化为红黑树
    35.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    36.                         treeifyBin(tab, hash);
    37.                     // 跳出循环
    38.                     break;
    39.                 }
    40.                 // 判断链表中结点的key值与插入的元素的key值是否相等
    41.                 if (e.hash == hash &&
    42.                     ((k = e.key) == key || (key != null && key.equals(k))))
    43.                     // 相等，跳出循环
    44.                     break;
    45.                 // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
    46.                 p = e;
    47.             }
    48.         }
    49.         // 表示在桶中找到key值、hash值与插入元素相等的结点
    50.         if (e != null) { 
    51.             // 记录e的value
    52.             V oldValue = e.value;
    53.             // onlyIfAbsent为false或者旧值为null
    54.             if (!onlyIfAbsent || oldValue == null)
    55.                 //用新值替换旧值
    56.                 e.value = value;
    57.             // 访问后回调
    58.             afterNodeAccess(e);
    59.             // 返回旧值
    60.             return oldValue;
    61.         }
    62.     }
    63.     // 结构性修改
    64.     ++modCount;
    65.     // 实际大小大于阈值则扩容
    66.     if (++size > threshold)
    67.         resize();
    68.     // 插入后回调
    69.     afterNodeInsertion(evict);
    70.     return null;
    71. }

    我们再来对比一下 JDK1.7 put方法的代码

    对于put方法的分析如下：

    ①如果定位到的数组位置没有元素 就直接插入。 ②如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和插入的key比较，如果key相同就直接覆盖，不同就采用头插法插入元素。

    1. public V put(K key, V value)
    2.     if (table == EMPTY_TABLE) { 
    3.     inflateTable(threshold); 
    4. }  
    5.     if (key == null)
    6.         return putForNullKey(value);
    7.     int hash = hash(key);
    8.     int i = indexFor(hash, table.length);
    9.     for (Entry<K,V> e = table; e != null; e = e.next) { // 先遍历
    10.         Object k;
    11.         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    12.             V oldValue = e.value;
    13.             e.value = value;
    14.             e.recordAccess(this);
    15.             return oldValue; 
    16.         }
    17.     }
    19.     modCount++;
    20.     addEntry(hash, key, value, i);  // 再插入
    21.     return null;
    22. }

    get方法

    1. public V get(Object key) {
    2.     Node<K,V> e;
    3.     return (e = getNode(hash(key), key)) == null ? null : e.value;
    4. }
    6. final Node<K,V> getNode(int hash, Object key) {
    7.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    8.     if ((tab = table) != null && (n = tab.length) > 0 &&
    9.         (first = tab[(n - 1) & hash]) != null) {
    10.         // 数组元素相等
    11.         if (first.hash == hash && // always check first node
    12.             ((k = first.key) == key || (key != null && key.equals(k))))
    13.             return first;
    14.         // 桶中不止一个节点
    15.         if ((e = first.next) != null) {
    16.             // 在树中get
    17.             if (first instanceof TreeNode)
    18.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    19.             // 在链表中get
    20.             do {
    21.                 if (e.hash == hash &&
    22.                     ((k = e.key) == key || (key != null && key.equals(k))))
    23.                     return e;
    24.             } while ((e = e.next) != null);
    25.         }
    26.     }
    27.     return null;
    28. }

    resize方法 进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。

    1. final Node<K,V>[] resize() {
    2.     Node<K,V>[] oldTab = table;
    3.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
    4.     int oldThr = threshold;
    5.     int newCap, newThr = 0;
    6.     if (oldCap > 0) {
    7.         // 超过最大值就不再扩充了，就只好随你碰撞去吧
    8.         if (oldCap >= MAXIMUM_CAPACITY) {
    9.             threshold = Integer.MAX_VALUE;
    10.             return oldTab;
    11.         }
    12.         // 没超过最大值，就扩充为原来的2倍
    13.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
    14.             newThr = oldThr << 1; // double threshold
    15.     }
    16.     else if (oldThr > 0) // initial capacity was placed in threshold
    17.         newCap = oldThr;
    18.     else { 
    19.         signifies using defaults
    20.         newCap = DEFAULT_INITIAL_CAPACITY;
    21.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    22.     }
    23.     // 计算新的resize上限
    24.     if (newThr == 0) {
    25.         float ft = (float)newCap * loadFactor;
    26.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    27.     }
    28.     threshold = newThr;
    29.     @SuppressWarnings({"rawtypes","unchecked"})
    30.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    31.     table = newTab;
    32.     if (oldTab != null) {
    33.         // 把每个bucket都移动到新的buckets中
    34.         for (int j = 0; j < oldCap; ++j) {
    35.             Node<K,V> e;
    36.             if ((e = oldTab[j]) != null) {
    37.                 oldTab[j] = null;
    38.                 if (e.next == null)
    39.                     newTab[e.hash & (newCap - 1)] = e;
    40.                 else if (e instanceof TreeNode)
    41.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    42.                 else { 
    43.                     Node<K,V> loHead = null, loTail = null;
    44.                     Node<K,V> hiHead = null, hiTail = null;
    45.                     Node<K,V> next;
    46.                     do {
    47.                         next = e.next;
    48.                         // 原索引
    49.                         if ((e.hash & oldCap) == 0) {
    50.                             if (loTail == null)
    51.                                 loHead = e;
    52.                             else
    53.                                 loTail.next = e;
    54.                             loTail = e;
    55.                         }
    56.                         // 原索引+oldCap
    57.                         else {
    58.                             if (hiTail == null)
    59.                                 hiHead = e;
    60.                             else
    61.                                 hiTail.next = e;
    62.                             hiTail = e;
    63.                         }
    64.                     } while ((e = next) != null);
    65.                     // 原索引放到bucket里
    66.                     if (loTail != null) {
    67.                         loTail.next = null;
    68.                         newTab[j] = loHead;
    69.                     }
    70.                     // 原索引+oldCap放到bucket里
    71.                     if (hiTail != null) {
    72.                         hiTail.next = null;
    73.                         newTab[j + oldCap] = hiHead;
    74.                     }
    75.                 }
    76.             }
    77.         }
    78.     }
    79.     return newTab;
    80. }

    HashMap常用方法测试

    1. import java.util.Collection;
    2. import java.util.HashMap;
    3. import java.util.Set;
    5. public class HashMapDemo {
    7.     public static void main(String[] args) {
    8.         HashMap<String, String> map = new HashMap<String, String>();
    9.         // 键不能重复，值可以重复
    10.         map.put("san", "张三");
    11.         map.put("si", "李四");
    12.         map.put("wu", "王五");
    13.         map.put("wang", "老王");
    14.         map.put("wang", "老王2");// 老王被覆盖
    15.         map.put("lao", "老王");
    16.         System.out.println("-------直接输出hashmap:-------");
    17.         System.out.println(map);
    18.         /**
    19.          * 遍历HashMap
    20.          */
    21.         // 1.获取Map中的所有键
    22.         System.out.println("-------foreach获取Map中所有的键:------");
    23.         Set<String> keys = map.keySet();
    24.         for (String key : keys) {
    25.             System.out.print(key+"  ");
    26.         }
    27.         System.out.println();//换行
    28.         // 2.获取Map中所有值
    29.         System.out.println("-------foreach获取Map中所有的值:------");
    30.         Collection<String> values = map.values();
    31.         for (String value : values) {
    32.             System.out.print(value+"  ");
    33.         }
    34.         System.out.println();//换行
    35.         // 3.得到key的值的同时得到key所对应的值
    36.         System.out.println("-------得到key的值的同时得到key所对应的值:-------");
    37.         Set<String> keys2 = map.keySet();
    38.         for (String key : keys2) {
    39.             System.out.print(key + "：" + map.get(key)+"   ");
    41.         }
    42.         /**
    43.          * 另外一种不常用的遍历方式
    44.          */
    45.         // 当我调用put(key,value)方法的时候，首先会把key和value封装到
    46.         // Entry这个静态内部类对象中，把Entry对象再添加到数组中，所以我们想获取
    47.         // map中的所有键值对，我们只要获取数组中的所有Entry对象，接下来
    48.         // 调用Entry对象中的getKey()和getValue()方法就能获取键值对了
    49.         Set<java.util.Map.Entry<String, String>> entrys = map.entrySet();
    50.         for (java.util.Map.Entry<String, String> entry : entrys) {
    51.             System.out.println(entry.getKey() + "--" + entry.getValue());
    52.         }
    54.         /**
    55.          * HashMap其他常用方法
    56.          */
    57.         System.out.println("after map.size()："+map.size());
    58.         System.out.println("after map.isEmpty()："+map.isEmpty());
    59.         System.out.println(map.remove("san"));
    60.         System.out.println("after map.remove()："+map);
    61.         System.out.println("after map.get(si)："+map.get("si"));
    62.         System.out.println("after map.containsKey(si)："+map.containsKey("si"));
    63.         System.out.println("after containsValue(李四)："+map.containsValue("李四"));
    64.         System.out.println(map.replace("si", "李四2"));
    65.         System.out.println("after map.replace(si, 李四2):"+map);
    66.     }
    68. }