HashMap、HashTable、ConcurrentHashMap使用和原理分析（以及内存优化）

2024-03-16 23:38:16

HashMap、HashTable、ConcurrentHashMap使用和原理分析（以及内存优化）

哈希码
每个对象和基本类型都有的一个方法 hashCode() 可以获取其hashCode
默认是对象的地址经过hash算法转换的整数

String aa = "123";
String bb = "456";
String cc = "123";
String dd = aa;

aa、cc、dd的hashCode均为 48690 bb为51669
hash值相等对象不一定一致
对象一致 hash值一定相等
因为他是一个散列算法

equals和== 比较的是对象的地址只有是同一个对象才返回true
只是String这种重写了equals方法只要同一个对象或者值相等就返回true

而Hash相关的数据结构如HashMap就是根据键对象的hash值来进行存放

HashMap

概念：
容量（capacity ）：默认16 一个桶中的容量
加载因子（load factor）：默认0.75 即桶中的可利用大小
链地址法：（开散列方法）：设散列表地址空间的位置从0~m-1，则通过对所有的Key用散列函数（hashCode()）计算出存放的位置，具有相同地址的关键码归于一个子集合（桶），在同一个Bucket中的键值对对象采用链表的方式链接起来

HashMap非线程安全的 HashTable线程安全，但是他是锁住整个整个table，ConcurrentHashMap也是线程安全的，锁的是segment

为什么HashMap线程不安全:
1 put()时，若两个线程都put了同样的hashcode的key，则值会被覆盖
3 当A线程put()数据时都发现空间不够，执行resize()时，而同时B线程也put()数据也发现空间不够执行resize()，有可能在A线程rehash()生成新表时节点i->k，而B线程rehash()生成新表时又将节点k->j，导致生成了死循环（i.next=k;k.next=i;）当一旦进入这个链表，就会导致死循环。
解决：使用ConcurrentHashMap（见下方）

HashMap时间复杂度
若美好的状态下没有hash冲突每个桶只有一个元素时间复杂度 O(1) ，最差是O(n) 红黑树则是O(logn)

HashMap原理/数据结构/HashMap怎么解决冲突的：
根本：数组 + 链表（jdk1.7）/数组+链表+红黑树（jdk1.8）（当链表长度超过阈值（8）将链表转为红黑树时间复杂度降低为O(logn)）
通过计算key的hash值，每个桶对应一个hash值，若发生了hash冲突，则将相同的元素作为链表的一个节点放到链表中

HashMap的hash算法

int index =（n-1) & key的hashcode

2^n长度的HashMap更高效，因为hash值计算后相同的概率更小，所以冲突更少一些因此默认长度为16，加载倍数也是2倍

HashMap怎么扩容resize()：若达到了阈值（容量*加载因子的大小），则会自动扩容2倍。jdk1.8在长度达到了8个时，还会升级为红黑树
扩容过程：基于新的容量重新执行reHash()算法，得到这些元素在新table中的位置并进行复制处理，因此扩容是很耗时的

HashMap的问题
1 当地址不够大时，HashMap会采用扩大当前空间两倍的方式去增大空间，而且在此过程中也需要不断的做hash运算，数据获取时也是通过遍历方式获取数据
2 当hash冲突较多，则链表会过长，遍历时间会过长

常见使用

构造函数
HashMap()
Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).
HashMap(int initialCapacity)
Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).
HashMap(int initialCapacity, float loadFactor)
Constructs an empty HashMap with the specified initial capacity and load factor.

1 size()
获取map的大小

2 isEmpty()
返回map 是否为空

3 get(Object key)
根据key返回value

4 containsKey(Object key)
根据key是否存在返回true or false

5 put(K key,V value)
装载键值对
对于put进了相同的key而不同的values。则后面的values会覆盖前面的values

6 putAll(Map< ? extends K,? extends V> m)
将形参的map的全部键值对传递给当前定义的map作为当前map的键值对

7 remove(Object key)
根据Key 移除 map中该键值对数据

8 clear()
清除map中所有数据

9 public Set keySet()
获取map中所有的key（key的遍历）
Set （集合中各元素唯一的）

for (String key : map.keySet()) {    
    System.out.println("key= "+ key);    
}

或者

Set<String> keySet = map.keySet();
		System.out.println(keySet);

10 public Collection values()
返回map中所有的values （values的遍历）

for (String v : map.values()) {    
    System.out.println("value= " + v);    
}

11 遍历map

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

12 public boolean remove(Object key,Object value)
移除键值对返回布尔值

13 replace(K key,V value)
替换键值对

Android中对HashMap的优化

1 通过 SparseArray稀疏数组的方式去节省内存空间
注意: key是为int 形式!!!
SparseArray: 由两个数组分别存放key 和 values
并且 key的存放为int形式，减少了装箱操作，采取了压缩的方式来表示稀疏数组的数据，并且通过二分查找方式去装载和读取数据

使用：

SparseArray<valueType> array = new SparseArray<>();

1 delete(int key) 或者 remove(int key)
移除key 对应的数据
2 get(int key)
获取key对应的键值对
3 put(int key, E value)
添加键值对
4 append(int key, E value)
也是添加键值对，若添加的键是按顺序递增的，则更推荐使用该方式，因为可以提高性能。
5 size()
获取SparseArray 大小

参考，官方文档：https://developer.android.com/reference/android/util/SparseArray.html

HashTable

基本原理和HashMap类似，线程安全的
key和value都不允许传null：因为多线程情况下，不同调用时机，无法确认key根本不存在，key值没有映射，还是值本身就是null的

只是用Synchronized对put()和get() 方法加锁(synchronized)
锁住的是整个table效率低

ConcurrentHashMap

基本原理与HashMap类似，但是是线程安全的
key和value都不允许传null：因为多线程情况下，不同调用时机，无法确认key根本不存在，key值没有映射，还是值本身就是null的

与HashTable锁住整个对象不同，ConcurrentHashMap采用锁分段技术，粒度更低，不是锁整个table，有一个Segment<K,V> extends ReentrantLock的数组（默认concurrencyLevel也是长度16，最大允许16个线程并发写操作），只对每个Segment加锁。不是同一个hash值的时候没必要加锁

segmentMask： length-1
segmentShift： 32 - lg （length）

假设ConcurrentHashMap一共分为2^ n个段，每个段中有2^m个桶
定位段的算法：

算法：hashCode & (2^n-1)
代码：向右无符号右移segmentShift位，然后和segmentMask进行与操作

定位桶的算法：

算法：hashCode & (2^m-1)

为什么读取可以不加锁：
用HashEntery对象的不变性来降低读操作对加锁的需求；
用Volatile变量协调读写线程间的内存可见性；
若读时发生指令重排序现象，则加锁重读

put()方法： lock()、unlock()加锁了
先定位段位置，再定位桶的位置。

resize()方法：
若达到了阈值（容量*加载因子的大小），则会自动扩容2倍。
扩容过程：基于新的容量重新执行reHash()算法(对ConcurrentHashMap的某个段的重哈希,因此ConcurrentHashMap的每个段所包含的桶位自然也就不尽相同)，得到这些元素在新table中的位置并进行复制处理，因此扩容是很耗时的

WeakHashMap

若将软/弱/虚引用对象当做key 所引用的对象作为value 即使回收了value 但是HashMap的大小还是不会变的，因为引用对象也是对象，引用对象本身并没有被回收，因此得用weakHashMap，当key中的引用被gc掉之后，它会将相应的entry给移除掉，原因就是检测ReferenceQueue是否为空是否软/弱/虚引用所引用的对象是否被回收
WeakHashMap是线程安全

LinkedHashMap

LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

是一个有序的HashMap，分为插入有序（默认）和访问有序
通过recordAccess标志位决定，true为访问顺序，默认为false

数据结构（怎么保证有序）：继承HashMap，和HashMap差不多，也是数组+链表（next指针），只是多了一个LinkedList双向链表，每个节点都有一个before、after指针

Entry节点结构：

使用场景：有序的HashMap，如实现LRU (Least recently used, 最近最少使用)算法

存储实现：
put:

 //1 根据key的hashCode通过hash算法： （n-1)&hashcode 得到在桶中的位置
int hash = hash(key.hashCode());           
//计算该键值对在数组中的存储位置（哪个桶）
int i = indexFor(hash, table.length);
//2 判断该条链上是否存在hash值相同且key值相等的映射，若存在，则直接覆盖 value
// 3 若不存在则创建新的Entry，并插入到LinkedHashMap中 
createEntry(hash, key, value, bucketIndex);
// 如果重写了removeEldestEntry返回true，并且accessOrder为true则支持LRU算法 默认返回false
Entry<K,V> eldest = header.after;  //双向链表的第一个有效节点（header后的那个节点）为最近最少使用的节点
if (removeEldestEntry(eldest)) {  
    removeEntryForKey(eldest.key);  //如果有必要，则删除掉该近期最少使用的节点
} else {  
    if (size >= threshold)  
        resize(2 * table.length);  //4 若超出了阈值，则扩容到原来的2倍  
}

利用LinkedHashMap实现LRU算法
Glide中就是使用了LinkedHashMap实现LRU算法:

public class LRU<K,V> extends LinkedHashMap<K, V> implements Map<K, V>{

@Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        // 关键是该函数返回true 则会移除最近最少使用的Entry
        if (size() > 6) {
            return true;
        }
        return false;
    }
// 这里的true也是必须的 将accessOrder置为true 使用访问顺序而非插入顺序
LRU<String,String> lru = LRU<String,String>(16,0.75,true);
正常使用put和get即可

码农公寓