Hashtable
、HashMap
、TreeMap
都是最常见的一些 Map
实现,是以键值对的形式存储和操作数据的容器类型。
Hashtable
是早期 Java
类库提供的一个哈希表实现,本身是同步的,不支持 null
键和值,由 于同步导致的性能开销,所以已经很少被推荐使用。
初始化与增长方式
HashTable
在不指定容量的情况下的默认容量为11,且不要求底层数组的容量一 定要为2的整数次幂;HashMap
默认容量为16,且要求容量一定为2的整数次幂。Hashtable
将容量变为原来的2倍加1;HashMap
扩容将容量变为原来的2倍。**HashMap
是应用更加广泛的哈希表实现,行为上大致上与 HashTable
一致,主要区别在于 HashMap
不是同步的,支持 null
键和值等。通常情况下,HashMap
进行 put
或者 get
操作,可以达到常数时间的性能,所以它是绝大部分利用键值对存取场景的首选,比如,实现一个 用户 ID 和用户信息对应的运行时存储结构。
HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap
;可能会导致数据 的不一致。如果需要同步:
Collections
的synchronizedMap
方法;ConcurrentHashMap
类,相较于HashTable
锁住的是对象整体, ConcurrentHashMap
基于lock
实现锁分段技术。首先将Map
存放的数据分成一段一段的存储方式,然后给每一段数据分 配一把锁,当一个线程占用锁访问其中一个段的数据时,其他段的数据也能被其他线程访问。ConcurrentHashMap
不仅保证了多线程运行环境下的数据访问安全性,而且性能上有 长足的提升。TreeMap
则是基于红黑树的一种提供顺序访问的 Map
,和 HashMap
不同,它的 get
、put
、 remove
之类操作都是 O(log(n))
的时间复杂度,具体顺序可以由指定的 Comparator
来决定,或者根据键的自然顺序来判断。
它是基于Map
接口的实现,存储键值对时,它可以接收null的键值,是非同步的,HashMap
存储着Entry(hash, key, value, next)
对象。
通过hash
的方法,通过put
和get
存储和获取对象。存储对象时,我们将K/V
传给put
方法时,它调用hashCode
计算hash
从而得到bucket
位置,进一步存储,HashMap
会根据当前bucket
的占用情况自动调整容量(超过Load Facotr
则resize
为原来的2倍)。获取对象时,我们将K
传给get
,它调用hashCode
计算hash
从而得到bucket
位置,并进一步调用equals()
方法确定键值对。如果发生碰撞的时候,Hashmap
通过链表将产生碰撞冲突的元素组织起来,在Java 8
中,如果一个bucket
中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。
通过对key
的hashCode()
进行hashing
,并计算下标( n-1 & hash)
,从而获得buckets
的位置。如果产生碰撞,则利用key.equals()
方法去链表或树中去查找对应的节点
在Java 1.8
的实现中,是通过hashCode()
的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16)
,主要是从速度、功效、质量来考虑的,这么做可以在bucket
的n比较小的时候,也能保证考虑到高低bit
都参与到hash
的计算中,同时不会有太大的开销。
如果超过了负载因子(默认0.75),则会重新resize
一个原来长度两倍的HashMap
,并且重新调用hash
方法。
HashMap
的性能表现非常依赖于哈希码的有效性,比如:
equals
相等,hashCode
一定要相等;hashCode
也要重写 equals
;hashCode
需要保持一致性,状态改变返回的哈希值仍然要一致;equals
的对称、反射、传递等特性;equals()
方法结果不变
x.equals(y) == x.equals(y); // truenull
的比较
对任何不是 null
的对象 x
调用 x.equals(null)
结果都为 false
x.equals(null); // false;它是按照key
的排序结果来组织内部结构的map
类集合,改变map
类散乱无序的现象。继承自abstractMap
,它有两个与众不同的接口,SortedMap
与NavigabableMap
,SortedMap
表示key
有序不可重复,支持获取哦图为key-value
元素,或者根据key
指定范围获取子集集合。插入key
必须实现camparable
或者提供额外的比较器comparator
,所以key
不允许为null
,但是value
可以。NavigabableMap
继承自SortedMap
,根据搜索条件返回最匹配key-value
。
不同于hashmap
,treepmap
并非一定要覆写hashcode
和equals
来达到key
去重目的。
CAS:它是解决轻微冲突的多线程并发场景下使用锁造成性能损耗的一种机制,cas
它是先比较,如果不符合预期,则进行重试,包含三个重要的操作要素:内存位置,预期原值与新值。
如果内存位置的值与预期原值相等,则处理器将该位置值更新为新值,如果不相等,则获取当前值,然后进行不断的轮询操作直到成果达到某个阙值退出。
早期 ConcurrentHashMap
,其实现是基于:
(Segment)
,里面则是 HashEntry
的数组,和 HashMap
类似,哈希相同的条目也是以链表形式存放。HashEntry
内部使用 volatile
的 value
字段来保证可见性,也利用了不可变对象的机制以改 进利用 Unsafe
提供的底层能力,比如volatile access
,去直接完成部分操作,以最优化性 能,毕竟 Unsafe
中的很多操作都是 JVM intrinsic
优化过的。在JDK11
中,它改造了三点:
(Segment)
,进一步降低冲突概率;map
原有的size
方法最大只能表达2的31次方减一,现在额外提供mappingCount
方法,最大表示为2的63次方减一,当元素更新时,使用多种优化和CAS
提高并发能力;Segment
定义,但仅仅是为了保证序列化时的兼容性而已,不再有任何结构 上的用处。因为不再使用 Segment
,初始化操作大大简化,修改为 lazy-load
形式,这样可以有效避免 初始开销,解决了老版本很多人抱怨的这一点;volatile
来保证可见性;CAS
等操作,在特定场景进行无锁并发操作;Unsafe
、LongAdder
之类底层手段,进行极端情况的优化;更多细节实现通过使用 Unsafe
进行了优化,例如 tabAt
就是直接利用 getObjectAcquire
,避免间接调用的开销。
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
}
table
长度为64,数据存储结构分为两种,链表与红黑树,当某个槽内元素个数增加到超过8个且table
容量大于或等于64,由链表转化成红黑树。当某个槽内元素减少到6个,又由红黑树转化成链表。当table
小于63时,只会扩容,不会转化成红黑树。
转化过程使用同步块锁住当前槽首元素,防止其他进程对当前槽进行增删改操作,转换完成,通过CAS
替换原有链表。因为TreeNode
节点也存储next
引用,所以只需从TreeBin
的first
元素开始遍历所有节点,并把节点从TreeCode
类型转化为Node
类型即可,当构造好新链表之后,会用CAS
替换原有的红黑树。