Java，数据结构和算法，八大数据结构，哈希表HashMap

Java，数据结构和算法，八大数据结构，哈希表HashMap

IT小奋斗2021-02-13 20:05:06

散列表（Hash table，也叫哈希表）

根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

HashMap重要参数说明：

1、initSize-->初始化大小

2、expansionFactor-->扩容因子

3、expansionMode-->扩容模式

当且仅当：实际大小乘以扩容因子小于长度（size*expansionFactor <= length），进行扩容，扩容为原来的2倍；

其他说明：

如果扩容因子越大，碰撞的概率也就越大，发生碰撞后的代价也更大，结果导致效率大打折扣。

因此扩容因子=0.75也是一个空间换时间的考虑，0.75这个数值应该是经过充分的考虑决定的。

ConcurrentHashMap

ConcurrentHashMap在性能以及安全性方面，明显比Collections.synchronizedMap()更加有优势；

1、SynchronizedMap的put封装了HashMap的put方法，并加上互斥锁保证了安全性；

2、JDK1.8的ConcurrentHashMap取消了segments字段，采用了transient volatile HashEntry<K,V>[] table保存数据；

· static class Segment<K,V> extends ReentrantLock implements Serializable；

· 这样对每个table数组元素加锁，可以减少并发冲突的概率，提高并发性能；

案例代码：

import java.io.Serializable;import com.what21.structure.map.hashmap.case01.mode01.MyMap;public class SynchronizedMap<K, V> implements MyMap<K, V>, Serializable {private static final long serialVersionUID = 1L;private MyMap<K, V> myMap;final Object mutex;public SynchronizedMap(MyMap<K, V> myMap) {this.myMap = myMap;this.mutex = this;}/** * @param myMap * @param mutex-->互斥锁 */public SynchronizedMap(MyMap<K, V> myMap, Object mutex) {this.myMap = myMap;this.mutex = mutex;}@Overridepublic void put(K key, V value) {synchronized (mutex) {this.myMap.put(key, value);}}@Overridepublic V get(K key) {synchronized (mutex) {return this.myMap.get(key);}}@Overridepublic void remove(K key) {synchronized (mutex) {this.myMap.remove(key);}}@Overridepublic int size() {synchronized (mutex) {return this.myMap.size();}}@Overridepublic void print() {synchronized (mutex) {this.myMap.print();}}}

public class SynchronizedMapDemo {public static void main(String[] args) {MyMap<Integer, String> hashMap = new SynchronizedMap<>(new MyHashMap<Integer, String>());System.out.println(hashMap);for (int i = 1; i < 40; i  ) {hashMap.put(i, 'value:'   i);}hashMap.print();}}

import java.util.Map;import java.util.concurrent.ConcurrentHashMap;public class ConcurrentHashMapDemo {public static void main(String[] args) {Map<Integer, String> hashMap = new ConcurrentHashMap<Integer, String>();System.out.println(hashMap);for (int i = 1; i < 40; i ) {hashMap.put(i, 'value:' i);}System.out.println(hashMap);}}

收藏

举报

0 条评论