HashMap源码解析
- 初始化信息
- 添加元素
- 删除元素
- 查找元素
- containsKey：指定的key是否在HashMap中
- containsValue：查找HashMap中是否有指定的value
- isEmpty
- indexFor：返回h在table数组中的位置
- 写在后面
初始化信息
//HashMap的初始容量，必须是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap的最大容量，必须是2的n次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//存储数据的Entry数组，每一个entry是一个链表
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
* 这个entry数组，随着需要改变大小，长度必须是2的n次幂
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//HashMap中元素的总个数
transient int size;
/**
* The next size value at which to resize (capacity * load factor).
* HashMap的阈值，用于判断是否需要调整HashMap的大小，threshold = capacity * load factor
* 初始大小 = 16 * 0.75 = 12
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold;
//加载因子实际大小
final float loadFactor;
//HashMap被改变的次数
transient int modCount;
//HashMap的默认阈值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
添加元素
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)//如果key为null,则将此value放到table[0]中的链表上
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);//如果没有重复的key，将当前元素放到table[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) {
/**
* 判断当前的数组大小和阈值的关系，如果当前阈值≤数组大小且table[bucketIndex]不为null，
* 就扩容，然后重新计算当前元素的位置
*/
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]的元素到e
table[bucketIndex] = new Entry<>(hash, key, value, e);//然后将e设置为新元素的下一个节点，新元素为该链表的头结点
size++;
//entry的构造方法如下
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
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));//将元素从移动到newTable中
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//重新调整阈值
}
/**
* Transfers all entries from current table to newTable.
*/
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;
}
}
}
删除元素
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) {//如果没有元素，返回null
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;
//查找到元素，删除单链表的节点
//只需将当前元素的前一个节点的下一个节点指向下下一个节点即可，即prev.next = next.next
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)//如果相等，表示删除的是第一个元素，所以要把table[i]指向next
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;//如果这个桶没有元素，返回null
}
查找元素
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;
}
containsKey：指定的key是否在HashMap中
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
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;
}
containsValue：查找HashMap中是否有指定的value
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}
isEmpty
public boolean isEmpty() {
return size == 0;
}
indexFor：返回h在table数组中的位置
/**
* Returns index for hash code h.这里用&运算代替了取模运算，加快了速度，因为HashMap中的长度都是按照2的幂增长的，所以，length - 1 换算成二进制就是1111111。。。；所以h&(length-1)和h%length在数值上时一致的，但是速度更快。
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
写在后面
异或运算（^）
//异或运算，转换为二进制，相同为0，不同为1
System.out.println(1^1);//0
System.out.println(1^0);//1
三目运算符
//三目运算符从左往右运算
int i = 1 > 0 ? 2 : 3 > 0 ? 7 : 8;
int j = 1 < 0 ? 2 : 3 > 0 ? 7 : 8;
System.out.println(i);//2
System.out.println(j);//7
hashcode值
同一个对象的hash值一定相同，同一个字符串的hash值一定相同；反之不一定。
两个对象相等，则hash值一定相同；反之不一定。
