1. hashmap的数据结构
数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。
数组
数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为o(1)；数组的特点是：寻址容易，插入和删除困难；
链表
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达o（n）。链表的特点是：寻址困难，插入和删除容易。
哈希表
那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表。哈希表（(hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。
哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 拉链法，我们可以理解为“链表的数组” ，如图：
从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
hashmap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里hashmap有做一些处理。
首先hashmap里面实现一个静态内部类entry，其重要的属性有key , value, next，从属性key,value我们就能很明显的看出来entry就是hashmap键值对实现的一个基础bean，我们上面说到hashmap的基础就是一个线性数组，这个数组就是entry[]，map里面的内容都保存在entry[]里面。
/** * the table, resized as necessary. length must always be a power of two. */ transient entry[] table;
2. hashmap的存取实现
既然是线性数组，为什么能随机存取？这里hashmap用了一个小算法，大致是这样实现：
// 存储时: int hash = key.hashcode(); // 这个hashcode方法这里不详述,只要理解每个key的hash是一个固定的int值 int index = hash % entry[].length; entry[index] = value; // 取值时: int hash = key.hashcode(); int index = hash % entry[].length; return entry[index];
1）put
疑问：如果两个key通过hash%entry[].length得到的index相同，会不会有覆盖的危险？
这里hashmap里面用到链式数据结构的一个概念。上面我们提到过entry类里面有一个next属性，作用是指向下一个entry。打个比方， 第一个键值对a进来，通过计算其key的hash得到的index=0，记做:entry[0] = a。一会后又进来一个键值对b，通过计算其index也等于0，现在怎么办？hashmap会这样做:b.next = a,entry[0] = b,如果又进来c,index也等于0,那么c.next = b,entry[0] = c；这样我们发现index=0的地方其实存取了a,b,c三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，hashmap的大致实现，我们应该已经清楚了。
我要评论
public v put(k key, v value) {
if (key == null)
return putfornullkey(value); //null总是放在数组的第一个链表中
int hash = hash(key.hashcode());
int i = indexfor(hash, table.length);
//遍历链表
for (entry<k,v> e = table[i]; e != null; e = e.next) {
object k;
//如果key在链表中已存在，则替换为新value
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;
}
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);//参数e, 是entry.next
//如果size超过threshold，则扩充table大小。再散列
if (size++ >= threshold)
resize(2 * table.length);
}
当然hashmap里面也包含一些优化方面的实现，这里也说一下。比如：entry[]的长度一定后，随着map里面数据的越来越长，这样同一个index的链就会很长，会不会影响性能？hashmap里面设置一个因子，随着map的size越来越大，entry[]会以一定的规则加长长度。
2）get
public v get(object key) {
if (key == null)
return getfornullkey();
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;
}
3）null key的存取
null key总是存放在entry[]数组的第一个元素。
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;
}
private v getfornullkey() {
for (entry<k,v> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
4）确定数组index：hashcode % table.length取模
hashmap存取时，都需要计算当前key应该对应entry[]数组哪个元素，即计算数组下标；算法如下：
/**
* returns index for hash code h.
*/
static int indexfor(int h, int length) {
return h & (length-1);
}
按位取并，作用上相当于取模mod或者取余%。
这意味着数组下标相同，并不表示hashcode相同。
5）table初始大小
public hashmap(int initialcapacity, float loadfactor) {
.....
// find a power of 2 >= initialcapacity
int capacity = 1;
while (capacity < initialcapacity)
capacity <<= 1;
this.loadfactor = loadfactor;
threshold = (int)(capacity * loadfactor);
table = new entry[capacity];
init();
}
注意table初始大小并不是构造函数中的initialcapacity！！
而是 >= initialcapacity的2的n次幂！！！！
————为什么这么设计呢？——
3. 解决hash冲突的办法开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列） 再哈希法 链地址法 建立一个公共溢出区
java中hashmap的解决办法就是采用的链地址法。
4. 再散列rehash过程
当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到integer.max_value返回，这时，需要创建一张新表，将原表的映射到新表中。
/**
* rehashes the contents of this map into a new array with a
* larger capacity. this method is called automatically when the
* number of keys in this map reaches its threshold.
*
* if current capacity is maximum_capacity, this method does not
* resize the map, but sets threshold to integer.max_value.
* this has the effect of preventing future calls.
*
* @param newcapacity the new capacity, must be a power of two;
* must be greater than current capacity unless current
* capacity is maximum_capacity (in which case value
* is irrelevant).
*/
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);
}
/**
* transfers all entries from current table to newtable.
*/
void transfer(entry[] newtable) {
entry[] src = table;
int newcapacity = newtable.length;
for (int j = 0; j < src.length; j++) {
entry<k,v> e = src[j];
if (e != null) {
src[j] = null;
do {
entry<k,v> next = e.next;
//重新计算index
int i = indexfor(e.hash, newcapacity);
e.next = newtable[i];
newtable[i] = e;
e = next;
} while (e != null);
}
}
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
如对本文有疑问， 点击进行留言回复！！
网友评论