Java容器HashMap与HashTable详解

Java容器HashMap与HashTable详解

1、HashMap

HashMap继承抽象类AbstractMap，实现接口Map、Cloneable, Serializable接口。HashMap是一种以键值对存储数据的容器，

由数组+链表组成，其中key和value都可以为空，key的值唯一。HashMap是非线程安全的， 对于键值对，

HashMap内部会将其封装成一个对应的Entry对象。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 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 getEntry(Object key) {

if (size == 0) {

return null;

}

int hash = (key == null) ? 0 : hash(key);

for (Entry 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链表的长度，来提高从HashMap中读取数据的速度。这是典型的拿空间换时间的策略。

但是我们不能刚开始就给HashMdXzVYUpcap分配过多的桶(即Entry[] table 数组起始不能太大)，这是因为数组是连续的内存空间，它的创建代价很大，况且我们不能确定给HashMap分配这么大的空间，它实际到底能够用多少，为了解决这一个问题，HashMap采用了根据实际的情况，动态地分配桶的数量。

要动态分配桶的数量，这就要求要有一个权衡的策略了，HashMap的权衡策略是这样的：

如果 HashMap的大小 > HashMap的容量(即Entry[] table的大小)*加载因子(经验值0.75)

则 HashMap中的Entry[] table 的容量扩充为当前的一倍；然后重新将以前桶中的`Entry`链表重新分配到各个桶中

上述的 HashMap的容量(即Entry[] table的大小) * 加载因子(经验值0.75)就是所谓的阀值(threshodXzVYUpcld)。

2、HashTable

HashTable继承Dictionary类，实现Map, Cloneable,Serializable接口，不允许key为空，采用拉链法实现与HashMap类似。

HashTable是线程安全的（但是在Collections类中存在一个静态方法：synchronizedMap()，该方法创建了一个线程安全的Map对象，通过该方法我们可以同步访问潜在的HashMap，对整个map对象加锁。CurrentHashMap是线程安全的，并且只对桶加锁，不会影响map对象上其它桶的操作）。

希望本文对各位朋友有所帮助

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。