源码剖析——HashMap、HashTable、HashSet的区别
1、HashMap
、HashTable
实际上是数组和链表的结合
2、HashMap
、HashTable
不允许添加相同key
,若添加了已经存在的key
,则会以最新的替代原来的,并返回上次的value
3、HashMap
允许添加key
或value
为null
,HashTable
不允许添加key
或value
为null
4、HashMap
线程不安全,性能高,HashTable
线程安全,方法中加synchronized
关键字,性能较差
5、HashSet
内部是基于HashMap
实现的,也就是hashMap
的key
形成了HashSet
,value
为
private static final Object PRESENT = new Object();
HashMap
元素key
相同的话,不会另外添加到HashMap
中,而是更新相同的key
的value
,这就保证了Hashset
不能存储相同的数据。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
6、内存扩容时采取的方式也不同,Hashtable
采用的是2*old+1
,而HashMap
是2*old
,HashSet
是2*old
。
7、剖析CRUD:
HashMap
&&HashTable
:
Create(增加):
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
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++;
}
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
思路:1、首先通过key
计算hash
值 然后得到在table[]
中的位置
2、然后根据put
顺序,新增的放在链头,最先的放在链尾,从而形成hashmap
结构为横向为数组table[]
,然后纵向为相同keyhash
值的Entry<K,V>
链表的形式。
Retrieve(查询):
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
思路:1、首先清楚结构是横向数组+纵向链表,首先利用key
算出hash
得到在数组中的索引值
2、得到索引值,然后e = e.next
遍历链表,key
相等则返回value
思考:首先初始化一个hashMap
然后先添加数据,直到table.length
发生改变,那么再get
,那么indexFor(hash, table.length)
的值不是和table.length
没发生改变前不一样吗,那么还能取出正确的数据吗?
多虑了,首先hashMap
每次put
,当里面的存储的数据大于table
的容量的时候,就会自动将table
的扩大2倍,看如下源码
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
在扩容的时候会重新生成一个空的数组,然后将老的数组中的数组重新按照新的table
生成hash
值,这样hashMap
中数据的次序也会发生改变,但是这样就会保证put
和get
的hash
都是同步的。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
Update(修改): (无)
Delete(删除):
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
思路:先找到然后和链表remove
方法差不多,修改prev、next
看一下:HashMap、HashTable、HashSet
都实现了java.io.Serializable
这个序列化的接口,并且里面存储数据的数组都用transient
关键字,然后利用writeObject
和readObject
两个方法来实现序列化操作时写入、读出。
推荐阅读
-
Java自学-集合框架 HashMap和Hashtable的区别
-
HashMap与Hashtable的区别 面试多线程框架
-
HashMap,LinkedHashMap,TreeMap,HashTable的区别 HashMapLinkedHashMapTreeMapHashTable
-
HashMap、HashTable、HashSet区别
-
HashTable、ConcurrentHashMap、TreeMap、HashMap关于键值的区别
-
【java】HashSet与HashMap的区别
-
Hashmap、Hashtable、Arraylist的区别
-
Hashmap、Hashtable、Arraylist的区别
-
HashMap与HashTable的区别(含源码分析)
-
HashMap和Hashtable的区别???