Java容器HashMap与HashTable详解
1、hashmap
hashmap继承抽象类abstractmap，实现接口map、cloneable, serializable接口。hashmap是一种以键值对存储数据的容器，
由数组+链表组成，其中key和value都可以为空，key的值唯一。hashmap是非线程安全的， 对于键值对<key,value>，
hashmap内部会将其封装成一个对应的entry<key,value>对象。hashmap的存储空间大小是可以动态改变的：
存储过程
每个对象都有一个对应的hashcode值，根据hashcode值，调用hash函数，计算出一个hash值，根据该hash值调用indexfor函数，计算出在table中的存储位置，如果该位置已经有值，则存储在该位置对应的桶中。
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;
}
public final int hash(object k) {
int h = hashseed;
if (0 != h && k instanceof string) {
return sun.misc.hashing.stringhash32((string) k);
}
h ^= k.hashcode();
// this function ensures that hashcodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
public final int hashcode() {
return objects.hashcode(getkey()) ^ objects.hashcode(getvalue())
}
static int indexfor(int h, int length) {
// assert integer.bitcount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
获取值
首先根据key的hashcode码计算出hash值，然后调用indexfor函数计算该entry对象在table中的存储位置，遍历该位置对应桶中存储的entry对象，如果存在对象的hash值和key与要查找的相同，则返回该对象。
public 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;
}
两map相等的判断
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;
}
自反性：对于任何非空引用值 x，x.equals(x) 都应返回 true。
对称性：对于任何非空引用值 x 和 y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 才应返回 true。
传递性：对于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回
true，那么 x.equals(z) 应返回 true。
一致性：对于任何非空引用值 x 和 y，多次调用 x.equals(y) 始终返回 true 或始终返回 false，前提是对象上
equals 比较中所用的信息没有被修改。
对于任何非空引用值 x，x.equals(null) 都应返回 false。
存储空间动态分配
hashmap的桶数目，即entry[] table数组的长度，由于数组是内存中连续的存储单元，它的空间代价是很大的，但是它的随机存取的速度是java集合中最快的。我们增大桶的数量，而减少entry<key,value>链表的长度，来提高从hashmap中读取数据的速度。这是典型的拿空间换时间的策略。
但是我们不能刚开始就给hashmap分配过多的桶(即entry[] table 数组起始不能太大)，这是因为数组是连续的内存空间，它的创建代价很大，况且我们不能确定给hashmap分配这么大的空间，它实际到底能够用多少，为了解决这一个问题，hashmap采用了根据实际的情况，动态地分配桶的数量。
要动态分配桶的数量，这就要求要有一个权衡的策略了，hashmap的权衡策略是这样的：
如果 hashmap的大小 > hashmap的容量(即entry[] table的大小)*加载因子(经验值0.75) 则 hashmap中的entry[] table 的容量扩充为当前的一倍；然后重新将以前桶中的`entry<key,value>`链表重新分配到各个桶中
上述的 hashmap的容量(即entry[] table的大小) * 加载因子(经验值0.75)就是所谓的阀值(threshold)。
2、hashtable
hashtable继承dictionary类，实现map, cloneable,serializable接口，不允许key为空，采用拉链法实现与hashmap类似。
hashtable是线程安全的（但是在collections类中存在一个静态方法：synchronizedmap()，该方法创建了一个线程安全的map对象，通过该方法我们可以同步访问潜在的hashmap，对整个map对象加锁。currenthashmap是线程安全的，并且只对桶加锁，不会影响map对象上其它桶的操作）。
希望本文对各位朋友有所帮助