HashMap的实现 非掌握知识点积累

#### HashMap是一种支持快速存储的数据结构,了解他的性能必要了解他的数据结构。
初始容量:加载因子(默认0.75,越大表示散列表中的装填程度越高,表示对一个散列表的空间使用程度)

#### 数据结构


底层基于数组, 每一项都为一条链。 构造函数 源码如下

//参数initialCapacity就代表了该数组的长度
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能 MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子不能 < 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(“Illegal load factor: ”
+ loadFactor);

// 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;

this.loadFactor = loadFactor;
//设置HashMap的容量极限,当HashMap的容量达到该极限时就会进行扩容操作
threshold = (int) (capacity * loadFactor);
//初始化table数组
table = new Entry[capacity];
init();
}
“`

每次创建一个HashMap时,都会初始化一个table数组,table数组的元素为Entry节点。

static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
final int hash;

/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
…….
}

其中Entry为HashMap的内部类,它包含了键key、值value、下一个节点next,以及hash值,正是由于Entry才构成了table数组的项为链表
#### put 存储实现

public V put(K key, V value) {

//当key为null,调用putForNullKey方法,保存null与table第一个位置中,这是HashMap允许为null的原因

if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = hash(key.hashCode()); ——(1)
//计算key hash 值在 table 数组中的位置
int i = indexFor(hash, table.length); ——(2)
//从i出开始迭代 e,找到 key 保存的位置
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
//判断该条链上是否有hash值相同的(key相同)
//若存在相同,则直接覆盖value,返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //旧值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回旧值
}
}
//修改次数增加1
modCount++;
//将key、value添加至i位置处
addEntry(hash, key, value, i);
return null;
}

先去通过Key的hash值寻找table链中的位置,如果存在value覆盖,不存在增加在链头。 新的Entry指向旧的Entry, 如果容量不够,扩容到两倍。
1. 允许key为NULL
2. 新Value替换旧Vlaue key不变
3. Hash的方法 :取模消耗太大。数据分布要均匀。

static int indexFor(int h, int length) {
return h & (length-1);
//这句话除了上面的取模运算外还有一个非常重要的责任:均匀分布table数据和充分利用空间。
}

4. 系统必须要在某个临界点进行扩容处理。该临界点在当HashMap中元素的数量等于table数组长度X加载因子,容量扩大两倍。所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
5. 在table存储的位置是相同的,也就是产生了碰撞,6、7就会在一个位置形成链表,这样就会导致查询速度降低
#### Get 实现:

public V get(Object key) {
// 若为null,调用getForNullKey方法返回相对应的value
if (key == null)
return getForNullKey();
// 根据该 key 的 hashCode 值计算它的 hash 码
int hash = hash(key.hashCode());
// 取出 table 数组中指定索引处的值
for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//若搜索的key与查找的key相同,则返回相对应的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

key的hash值找到在table数组中的索引处的Entry,然后返回该key对应的value即可。

Advertisements
HashMap的实现 非掌握知识点积累

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s