java_集合
2018-05-21 本文已影响19人
飞翔的鲲
关系图
image.png
HashMap（jdk1.7）
注意：
key需要存储不可变对象，如String。如果存储可变对象，hashCode会变，数据可能会找不到。
-
结构
image.png
-
数组长度为2的n次方。
-
计算key的hash值
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
- 散列为数组下标
static int indexFor(int h, int length) {
return h & (length-1);
}
这种方式类似于取模散列，但效率更高。
- put数据过程
1）先通过要存入的数据key的hash值找到对应的链表
2）遍历链表通过key的地址比较或值比较查找此key是否已经存在，如果存在就对应的value设置成新值，如果没有就在链表头添加新entity
public V put(K var1, V var2) {
if (this.table == EMPTY_TABLE) {
this.inflateTable(this.threshold);
}
if (var1 == null) {
return this.putForNullKey(var2);
} else {
int var3 = this.hash(var1);
int var4 = indexFor(var3, this.table.length);
for(HashMap.Entry var5 = this.table[var4]; var5 != null; var5 = var5.next) {
if (var5.hash == var3) {
Object var6 = var5.key;
// 这里判断key是否已经存在
if (var5.key == var1 || var1.equals(var6)) {
Object var7 = var5.value;
var5.value = var2;
var5.recordAccess(this);
return var7;
}
}
}
++this.modCount;
this.addEntry(var3, var1, var2, var4);
return null;
}
}
- 添加数据
总是添加在链表头部，即table下标地址处。
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
-
先创建新entity并指向table第n个结点
-
再将table第n个结点指向新entity
-
rehash扩容
HashMap对象不变，只是将table改成了新table。
void resize(int var1) {
HashMap.Entry[] var2 = this.table;
int var3 = var2.length;
if (var3 == 1073741824) {
this.threshold = 2147483647;
} else {
HashMap.Entry[] var4 = new HashMap.Entry[var1];
// 将之前数据拷贝到新map里
this.transfer(var4, this.initHashSeedAsNeeded(var1));
this.table = var4;
this.threshold = (int)Math.min((float)var1 * this.loadFactor, 1.07374182E9F);
}
}
3.1 扩容数据变化过程
将此entity指向链表头entity，在将此entity放入链表头，即table[n]。
重点：map数据拷贝过程中不会创建新数据对象，只是将之前数据对象指向地址改变。
1）遍历table内的每一个链表
2）遍历一个链表时，拿出这个entity，如果是新table的第一个，entity的next 指向table[n], 即指向null。再取去新entity，如果table[n]链表上有数据，next指向链表头entity，再将此entity放入链表头。
简单理解：
遍历原来的hashMap（遍历方式，先遍历Entry 数组，取出table[0]这个entry，再遍历这个链表遍历，完成hashMap的遍历。），每取出一个Entry，通过其key 算出在新Entry table里的下标，将其放在table对应位置，这个entry即这个链表的头。所以链表存储的顺序相对来说跟之前是反的。
void transfer(HashMap.Entry[] var1, boolean var2) {
int var3 = var1.length;
HashMap.Entry[] var4 = this.table;
int var5 = var4.length;
HashMap.Entry var8;
for(int var6 = 0; var6 < var5; ++var6) {
for(HashMap.Entry var7 = var4[var6]; null != var7; var7 = var8) {
var8 = var7.next;
if (var2) {
var7.hash = null == var7.key ? 0 : this.hash(var7.key);
}
int var9 = indexFor(var7.hash, var3);
var7.next = var1[var9];
var1[var9] = var7;
}
}
}
hashMap（jdk1.8）
Java 8系列之重新认识HashMap
https://tech.meituan.com/java-hashmap.html
hashMap在Java1.7与1.8中的区别
https://www.cnblogs.com/stevenczp/p/7028071.html
对1.7的hashMap做了优化，大数据量的时候性能会更好。
改变点：
- 当链表长度超过8时会转变为红黑树
- 使用Node[]数组
- rehash的时候方法做了优化
- key需要实现compare接口，性能才会提升
HashTable
与hashmap的主要区别：
- 方法加了synchronized锁实现线程安全。
- 直接使用对象的hashCode
- 映射数组地址直接使用取模方式
- hashTable不需要数组长度为2的幂次方
- HashTable不允许key和value为null
还可以使用Collections.SynchronizedMap()实现线程安全。
主要使用了对象锁，对map的操作加了锁。
public V put(K var1, V var2) {
Object var3 = this.mutex;
synchronized(this.mutex) {
return this.m.put(var1, var2);
}
}
ConcurrentHashMap
ConcurrentHashMap实现原理及源码分析http://www.cnblogs.com/chengxiao/p/6842045.html
分段锁：
HashTable性能差主要是由于所有操作需要竞争同一把锁，而如果容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，
image.png
- put
1.定位segment并确保定位的Segment已初始化
2.调用Segment的put方法。
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
- segment.put
多线程操作不同段是不会并发枷锁。同时访问一个segment时，需要加锁。这里使用了ReentrantLock，操作前加锁，操作完解锁。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
- get
由于value是volatile修饰的，内存修改具有可见性，所以不需要枷锁。
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
}
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
treeMap
使用的是红黑树。
