哈希表,HashMap,Hashtable,ConcurrentHashMap,WeakHashMap,ThreadLocal,集合

哈希表:

在哈希表中进行添加,删除,查找等操作,性能十分高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1);数据结构的物理存储结构只有两种:顺序存储结构和**链式存储结构。**例如数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组。比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。

                                                      存储位置 = f(关键字)

**** 其中,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作:

查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

哈希冲突:
如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突
,也叫哈希碰撞。

哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单散列地址分布均匀,但是再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种,而HashMap即是采用了链地址法,也就是数组+链表的方式。

简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好 

HashMap:

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。

Entry.key和Entry.value均可以为null

扩容时扩容一倍

1//初始化容量 16 2static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 3 4//最大容量 2的30次方 5static final int MAXIMUM_CAPACITY = 1 << 30; 6 7//负载因子,使用率大于0.75即扩容 8static final float DEFAULT_LOAD_FACTOR = 0.75f; 9

线程不安全:

    1.hash碰撞时,next指向会产生丢失;

    2.扩容添加时,拷贝本数据,并添加当前线程添加的数据,并返回该对象给引用。会丢失另一线程的数据

  key的hashCode与equals方法

1//HashMap获取value,先根据hash值去获取 2public V get(Object key) { 3 Node<K,V> e; 4 return (e = getNode(hash(key), key)) == null ? null : e.value; 5} 6
1public class MyTest { 2 private static class Person{ 3 int idCard; 4 String name; 5 6 public Person(int idCard, String name) { 7 this.idCard = idCard; 8 this.name = name; 9 } 10 11 @Override 12 public boolean equals(Object o) { 13 if (this == o) { 14 return true; 15 } 16 if (o == null || getClass() != o.getClass()){ 17 return false; 18 } 19 Person person = (Person) o; 20 return this.idCard == person.idCard; 21 } 22 23 } 24 public static void main(String []args){ 25 HashMap<Person,String> map = new HashMap<Person, String>(); 26 Person person = new Person(1234,"乔峰"); 27 map.put(person,"天龙八部"); 28 System.out.println("结果:"+map.get(new Person(1234,"萧峰"))); 29 } 30} 31 32结果:null 33 34

由于没有重写hashCode方法,通过key取出value的时候 key(hashcode1)-->hash-->indexFor-->最终索引位置,由于hashcode1不等于hashcode2,导致没有定位到一个数组位置而返回逻辑上错误的值null。

所以,在重写equals的方法的时候,必须注意重写hashCode方法,同时还要保证通过equals判断相等的两个对象,调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象,其hashCode可以相同(只不过会发生哈希冲突,应尽量避免)

Hashtable

 是线程安全的,相对于HashMap的最大特点就是线程安全,所有的操作都是被synchronized锁保护的,不允许null的key和value。初始size为11,扩容:newsize = olesize * 2 + 1,负载因子0.75

1public Hashtable() { 2 this(11, 0.75f); 3} 4
1 public synchronized V put(K key, V value) {。。。} 2 3 public synchronized V get(Object key) {。。。。} 4

ConcurrentHashMap

底层采用分段的数组+链表实现,线程安全通过把整个Map分为N个Segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry的value变量是 volatile的,也能保证读取到最新的值。

Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁。

扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容

ConcurrentHashMap的并发度就是segment的大小,默认为16,这意味着最多同时可以有16条线程操作Map,这也是 ConcurrentHashMap对Hashtable的最大优势

WeakHashMap

WeakHashMap的key是“弱键”,即是WeakReference类型的;键被回收时,它对应的键值对也就从映射中有效地移除。

  1. 新建WeakHashMap,将“键值对”添加到WeakHashMap中。实际上,WeakHashMap是通过数组table保存Entry(键值对);每一个Entry实际上是一个单向链表,即Entry是键值对链表
  2. 当某“弱键”不再被其它对象引用,并被GC回收时。在GC回收该“弱键”时,这个“弱键”也同时会被添加到ReferenceQueue(queue)队列中
  3. 当下一次我们需要操作WeakHashMap时,会先同步table和queue。table中保存了全部的键值对,而queue中保存被GC回收的键值对;同步它们,就是删除table中被GC回收的键值对。

这就是“弱键”如何被自动从WeakHashMap中删除的步骤了。和HashMap一样,WeakHashMap是不同步的。可以使用 Collections.synchronizedMap 方法来构造同步的 WeakHashMap。

ThreadLocal:

key是Thread对象的弱引用,当key被gc后,会出现value的gc可达,应用不可达,有内存泄漏风险

ArrayList:

1private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//初始化数据 2private static final int DEFAULT_CAPACITY = 10;//初始化容量 3public ArrayList() { 4 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 5} 6 7//扩容,1--》1.5倍数 8private void grow(int minCapacity) { 9 int oldCapacity = elementData.length; 10 int newCapacity = oldCapacity + (oldCapacity >> 1); 11 if (newCapacity - minCapacity < 0) 12 newCapacity = minCapacity; 13 if (newCapacity - MAX_ARRAY_SIZE > 0) 14 newCapacity = hugeCapacity(minCapacity); 15 elementData = Arrays.copyOf(elementData, newCapacity); 16} 17

Vector:

LinkList:

HashSet:

线程不安全,存取速度快,底层实现是一个HashMap

默认初始容量为16;加载因子为0.75;扩容增量:原容量的 1 倍

代码交流 2021