android整理之HashMap
2018-05-01 本文已影响0人
源来是你啊
HashMap简介
HashMap基于哈希表的 Map 接口的实现，继承自AbstractMap。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。但是它不是线程安全的集合，只能在单线程内操作数据（ConcurrentHashMap是线程安全的）。
HashMap数据结构
HashMap是基于数组和链表实现的：HashMap首先创建了一个数组，然后这个数组的每个元素都是一个链表的头结点。当HashMap存储一个元素时，首先获取key.hashCode()来计算此元素的hash值，然后通过indexFor函数计算它应该存储在哈希数组的哪个下标链表里面。通过这样的方式避免了哈希散列冲突，也增加了查询速度。
hashmap数据结构
解释一下：图中，0~15部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。
当然解决hashmap散列冲突的方法:开放定址法和拉链法，这里我们介绍一下拉链法:
从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点Bucket桶。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
源码分析
首先看一下hashmap的关键属性变量:
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*这就是存储链表的哈希数组
*/
transient Entry[] table;
/**
* The number of key-value mappings contained in this map.
* 元素的个数
*/
transient int size;
/**
* The next size value at which to resize (capacity * load factor).
* 临界值
*/
int threshold;
/**
* The load factor for the hash table.
*
* 加载因子
*/
final float loadFactor;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
* 被修改的次数
*/
transient volatile int modCount;
①loadFactor:加载因子 表示这个哈希表被填满的程度，若加载因子越大，则表明表中元素越多，空间利用率越高，但散列冲突会增加，查询速度会降低；
②所以如果对内存足够需要查询速度，就可以把叫矮子啊因子设置小一点；以空间换时间；
接下来看一下HashMap的构造方法：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
//capacity 表容量 initialCapacity初始化容量
//算数左移 每次乘2 所以capacity是2的n次幂
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
//临界值为容量乘以加载因子
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
在此之前先介绍一下哈希数组的实体类Entry:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;//元素键
V value;//元素值
Entry<K,V> next;//下一个元素
final int hash;//哈希值
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
由上述Entry我们知道，哈希数组的每个元素都维护了一个键值对、哈希值和下一元素的地址；
接下来我们看一看数据的储存于获取:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//通过key.hashCode()生成相应的hash值
int hash = hash(key.hashCode());
//通过哈希数组的长度和hash值计算此元素应该被存储在哪个位置
int i = indexFor(hash, table.length);
//在第i条链表遍历 查看元素是否存在
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;//若存在则返回旧值
}
}
//若不存在则添加新值 并返回null
modCount++;
addEntry(hash, key, value, i);
return null;
}
addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
若临界值小于表容量，则将表的容量扩大两倍:
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);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
若临界值已经达到i最大整型值，则返回；否则重新创建一个哈希数组，并通过transfer重新计算hash值并且复制到新的哈希数组中(很耗时)，最后重新定义临界值.
接下来我们看一下数据的获取:
public V get(Object key) {
if (key == null)
return getForNullKey();
//计算hash值
int hash = hash(key.hashCode());
//计算在那条链表上 并遍历
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.equals(k)))
return e.value;
}
return null;
}
至此hashmap源码解析完毕.
