Java容器

1. Map接口

1. 常用实现类

• HashMap

  • 它根据key的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却不确定
  • 最多只允许一条记录的key为null，允许多条记录的value为null
  • 非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 ConcurrentHashMap或者Collections.synchronizedMap方法使HashMap具有线程安全的能力

• LinkedHashMap

  • LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序

• TreeMap

  • TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。
  • 在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException

• Hashtable

  • Hashtable是遗留类(不建议在新代码中使用)，很多映射的常用功能与HashMap类似，不同的是它继承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁
  • 不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换

Note: 对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

2. equals() vs hashCode()

1. equals

• 判断两个对象是否相等，Object默认实现为判断两个对象地址是否相等
• ==判断两个对象地址是否相等，即两个对象是否是同一个对象

2. hashCode

• 获取哈希码，仅当创建某个类的散列表时才有作用
• 如果两个对象相等，那么哈希码一定相同；如果两个对象哈希码相等，对象不一定相等。即equals相同，hashCode一定相同；hashCode相同，equals不一定相同

3. 重写equals方法

• 自反性：对于任何非null的引用值x, x.equals(x) 必须返回 true
• 对称性：对于任何非null的引用值x和y，当且仅当x.equals(y) 返回true时， y.equals(x)必须返回true
• 传递性： 对于任何非null的引用值x，y和z，如果x.equals(y)返回true，并且y.equals(z)也返回true,那么x.equals(z)也必须返回true
• 一致性：对于任何非null的引用值x和y, 只要equals的比较操作在对象中所用的信息没有被修改，多次调用x.equals(y)就会一致的返回true,或者一致的返回false
• 对于任何非null的引用值x，x.equals(null)必须返回false

例子：

39 @Override
40 public boolean equals(Object obj){  
41     if(obj == null){  
42         return false;  
43     }  
44       
45     //如果是同一个对象返回true，反之返回false  
46     if(this == obj){  
47         return true;  
48     }  
49       
50     //判断是否类型相同  
51     if(this.getClass() != obj.getClass()){  
52         return false;  
53     }  
54       
55     Person person = (Person)obj;  
56     return name.equals(person.name) && age==person.age;  
57 } 

4. 重写hashCode方法

• hashCode 方法与 equals 方法应使用相同的字段，这样可以实现第一条约定。
• 若 hashCode 方法使用的字段总体上呈某种概率分布，则可利用概率论的知识构造出总体呈均匀分布的散列码。

工具：

· ^                           //异或运算符
·<< or >> or >>>              //左移运算符或右移运算符
·13、17、31、1231、1237       //重写 hashCode 方法时常用的素数
·hashCode()                      //每一个类都自带的方法
·Objects.hashCode(Object o)      //return o != null ? o.hashCode() : 0;
·Objects.hash(Object... values) //return Arrays.hashCode(values);  
·Arrays.hashCode(Object[] a) 及其重载方法
·包装器的静态方法 hashCode

3. HashMap

1. 数据结构（数组 + 链表/红黑树）

1. 数组

• 存储区间连续
• 寻址容易（O(1)），插入、删除困难（O(n)）

2. 链表

• 存储区间离散
• 寻址困难（O(n)），插入、删除容易（O(1)）

3. 红黑树

• O(logn)

4. Node

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

5. 一个实例

map.put("美团","小美");

1. 调用”美团”这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象）
2. 然后再通过Hash算法的后两步运算（高位运算和取模运算，下文有介绍）来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。

6. 几个参数

int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  
int size;  

• HashMap数组长度默认容量length为16（必须是2的n次方【合数】），loadFactor为负载因子（默认0.75），threshold是HashMap能容纳的最大键值对个数，threshold = length * loadFactor。
• 当实际存储的键值对个数size超过threshold时，需要重新resize（扩容），扩容后HashMap容量length是之前的2倍（实现位操作等同于取模的基础）。
• modCount记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。

2. 确认哈希桶数组索引位置

方法一：
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

1. 取key的hashCode值

2. 高位运算

   JDK1.8中，优化了高位运算的算法，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

3. 取模运算

   在length总是2的n次方的前提下，h & (length -1)（按位与）运算等价于h % length(取模)运算，但&比%有更高的效率。

3. Put

1. 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
2. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3；
3. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；
4. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；
5. 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
6. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

4. 扩容机制

当HashMap中实际存储的键值对个数size超过threshold时，需要重新resize（扩容）。

• 创建一个新的哈希桶，将旧的哈希桶中的数据复制到新的哈希桶中，扩容过程涉及到rehash、复制数据，非常耗性能（建议提前预估HashMap大小，减少扩容带来的性能损耗）
• 扩容后HashMap容量length是之前的2倍，最大是2^30

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

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

5. Fast-fail

在使用迭代器的过程中如果HashMap被修改，那么ConcurrentModificationException将被抛出，也即Fast-fail策略。

6. JDK1.8的优化

1. 头插法 -> 尾插法（避免多线程环境环形链表，造成死循环）
2. 链表（时间复杂度：O(n)） -> 红黑树（时间复杂度：O(logn)）
3. 我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，无需重新计数hash，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置

7. 线程安全性

HashMap线程不安全，多线程环境会造成死循环(JDK1.8修复)，多线程环境建议使用ConcurrentHashMap。

因为在 put 元素的时候，如果触发扩容操作，也就是 rehash ，就会将原数组的内容重新 hash 到新的扩容数组中，但是在扩容这个过程中，其他线程也在进行 put 操作，如果这两个元素 hash 值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。

1. ConcurrentHashMap(推荐)

• key、value都不为空，否则抛出NullPointerException

• 支持通过Iterator遍历同时修改HashMap

• 延迟初始化，在put时才初始化哈希桶(initTable)

• Segment分段锁（继承ReentrantLock可重入锁）：将整个哈希桶分解成多个Segment对象，每个Segment对象可以看作是一个细粒度的哈希桶；理论上可支持concurrencyLevel（等于Segment的个数）个线程安全的并发读写。

• JDK1.8实现

  • Segment分段锁 -> CAS机制（效率高，但CPU资源消耗多） + synchroized（自旋次数超过阈值时切换位互斥锁）

  • CAS(Compare and Swap)机制

    CAS 通过将内存中的值与期望值进行比较，只有在两者相等时才会对内存中的值进行修改，CAS 是在保证性能的同时提供并发场景下的线程安全性。

    • 原子操作的一种，能保证一次读写操作是原子的
    • AtomicInteger
    • 缺点
      1. 循环检查的时间可能较长，不过可以限制循环检查的次数
      2. 只能对一个共享变量执行原子操作
      3. 存在 ABA 问题（ABA 问题是指在 CAS 两次检查操作期间，目标变量的值由 A 变为 B，又变回 A，但是 CAS 看不到这中间的变换，对它来说目标变量的值并没有发生变化，一直是 A，所以 CAS 操作会继续更新目标变量的值。）

2. CollectionUtils.synchronizedMap()

• 粗粒度的同步方式，在高并发情况下，性能比较低下
• SynchronizedMap静态内部类，Object mutex互斥锁，put、get、size 等各种方法加上synchronized关键字

3. HashTable

• 遗留类，建议用ConcurrentHashMap替换
• 粗粒度的同步方式，在高并发情况下，性能比较低下
• put、get、size 等各种方法加上synchronized关键字

4. LinkedHashMap

• 有序（插入顺序或访问顺序）
• 线程不安全

1. 基本结构

• HashMap + LinkedList

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
  /**
  * The head of the doubly linked list.
  * 双向链表的头节点
  */
  private transient Entry<K,V> header;
  /**
  * The iteration ordering method for this linked hash map: true
  * for access-order, false for insertion-order.
  * true表示最近最少使用次序，false表示插入顺序
  */
  private final boolean accessOrder;
}

• 元素

private static class Entry<K,V> extends HashMap.Entry<K,V> {
  // These fields comprise the doubly linked list used for iteration.
  Entry<K,V> before, after;

  Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
    super(hash, key, value, next);
  }
  ...
}

2. List接口

3. 参考

• Java 8系列之重新认识HashMap
• 从ConcurrentHashMap的演进看Java多线程核心技术

Java容器

原文：https://www.cnblogs.com/jay-code-life/p/15217527.html