一:HashMap
--->底层存储的是Entry<K,V>[]数组
--->Entry<K,V>的结构是一个单向的链表
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
--->存储或移除的定位。
(1)存储key的时候,先取key的hascode,然后对hascode进行一系列的按位与,按位异或运算最终得到一个数字,再拿这个数字和Entry[]数组的长度减一进行按位与运算,求出要存储的数组下标。
(2)拿到数组上的entry对象,然后遍历,对key的hashcode比较。如果hashcode相同,再进行equals比较内容。如果都相同,则表示是同一个key,则进行替换。如果没有相等的,则new一个entry对象,加到链表的末尾。
(3)如果拿对象作为key的话。一定要重写这个对象的hashcode方法和equals方法。确保存储和查找正常。
(4)不同的对象hascode可能会相同,因此一定要重写equals方法。
二:ConcurrentHashMap
--->底层是一个Segment<K,V>[]数组。先对key进行hash运算,得到segment数组的下标,然后将数据存放到segment对象内部的HashEntry数组中去。这个存放和hasMap就一致了。
--->Segment<K,V>对象又是继承重入锁的ReentrantLock的对象。
--->每个Segment元素内部又存储了一个HashEntry<K,V>[]数组
--->将来每个key-value对是转化成HashEntry对象。
--->HashEntry的结构又是单向链表结构
--->该类利用了Unsafe类提供的cas操作和线程锁的方法。实现线程安全和高效。所谓的分段锁技术,就是将元素存储在多个容器中,每个容器都有自己的一把锁。将单个锁的压力分摊给多个锁。大大减少了互斥的发生。又因为没有使用synchronized的重量级锁。使用的是并发包的锁机制。而并发包的锁机制,依赖的是jdk的unsafe类提供的原子操作,和线程阻塞技术实现的同步。
--->存的时候使用了锁。
--->读的时候利用的unsafe提供的voliate语意直接读取内存的方法。
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}