Java容器

1. Map接口

Java容器

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的引用值xy,当且仅当x.equals(y) 返回true时, y.equals(x)必须返回true
  • 传递性: 对于任何非null的引用值xyz,如果x.equals(y)返回true,并且y.equals(z)也返回true,那么x.equals(z)也必须返回true
  • 一致性:对于任何非null的引用值x和y, 只要equals的比较操作在对象中所用的信息没有被修改,多次调用x.equals(y)就会一致的返回true,或者一致的返回false
  • 对于任何非null的引用值xx.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. 数据结构(数组 + 链表/红黑树)

Java容器

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(取模)运算,但&比%有更高的效率

Java容器

3. Put

Java容器

  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的个数)个线程安全的并发读写。

Java容器

  • 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互斥锁,putgetsize 等各种方法加上synchronized关键字
3. HashTable
  • 遗留类,建议用ConcurrentHashMap替换
  • 粗粒度的同步方式,在高并发情况下,性能比较低下
  • putgetsize 等各种方法加上synchronized关键字

4. LinkedHashMap

  • 有序(插入顺序或访问顺序)
  • 线程不安全

1. 基本结构

Java容器

  • 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容器

上一篇:Spring Boot 入门系列(二十三)整合Mybatis,实现多数据源配置!


下一篇:Okhttp介绍及使用