JDK1.6中文版的对HashMap -

ssydxa219

浏览: 622539 次
性别:
来自: 杭州

最近访客更多访客>>

jmi_hua

依然任逍遥

gaojingsong

jveqi

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

JDK1.6中文版的对HashMap

博客分类：

java core

以下是 JDK1.6 中文版的对 HashMap 的具体介绍：

    基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外， HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
    此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（ get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的 “容量 ”（桶的数量）及其大小（键 -值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
    HashMap 的实例有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
    通常，默认加载因子 (0.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
    如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。
下面是 HashMap 中的方法：

void clear() 从此映射中移除所有映射关系。

Object clone() 返回此 HashMap 实例的浅表副本：并不复制键和值本身。

boolean containsKey(Object key) 如果此映射包含对于指定键的映射关系，则返回 true。

boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值 ,则返回 true。

Set<Map.Entry<K,V>> entrySet() 返回此映射所包含的映射关系的 Set 视图。

V get(Object key) 返回指定键所映射的值；如对于该键来说，此映射不包含任何映射关系，则返回 null。

boolean isEmpty() 如果此映射不包含键 -值映射关系，则返回 true。

Set<K> keySet() 返回此映射中所包含的键的 Set 视图。

V put(K key, V value) 在此映射中关联指定值与指定键。

void putAll(Map<? extends K,? extends V> m)

将指定映射的所有映射关系复制到此映射中，这些映射关系将替换此映射目前针对指定映射中所有键的所有映射关系。

V remove(Object key) 从此映射中移除指定键的映射关系（如果存在）。

int size() 返回此映射中的键 -值映射关系数。

Collection<V> values() 返回此映射所包含的值的 Collection 视图。

下面深入 HashMap 源代码，详解它的具体实现：

一、 HashMap 的数据结构 ： HashMap用了一个名字为 table的 Entry类型数组；数组中的每一项又是一个 Entry链表。

// 默认的初始化大小 : static final int DEFAULT_INITIAL_CAPACITY = 16;

// 最大的容量 : static final int MAXIMUM_CAPACITY = 1 << 30;

// 负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 储存 key-value键值对的数组，一个键值对对象映射一个 Entry对象

transient Entry[] table;

// 键值对的数目 transient int size;

// 调整 HashMap大小门槛，该变量包含了 HashMap能容纳的 key-value对的极限，它的值等于 HashMap的容量乘以负载因子

int threshold;

// 加载因子 final float loadFactor;

// HashMap结构修改次数 ,防止在遍历时，有其他的线程在进行修改

transient volatile int modCount;

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 的大小为 2的幂，至于为什么，请看下面

while (capacity < initialCapacity)

capacity <<= 1;

this.loadFactor = loadFactor;

threshold = (int) (capacity * loadFactor);

table = new Entry[capacity];

init();

}

下面是用于包装 key-value映射关系的 Entry，它是 HashMap的静态内部类：

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) {

}

二、下面我们看看 HashMap 的 put 和 get 及 remove 方法源码，就知道为什么说它数据结构是链表和数组了

// 根据 key获取 value

public V get(Object key) {

if (key == null)

return getForNullKey();

//根据 key的 hashCode值计算它的 hash码

int hash = hash(key.hashCode());

//直接取出 table数组中指定索引处的值

for (Entry<K, V> e = table[indexFor(hash, table.length)];

e != null;

//搜索该 Entry链的下一个 Entry

e = e.next) {

Object k;

//如果该 Entry的 key与被搜索 key相同

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

return e.value;

}

return null;

}

private V getForNullKey() {

//key为 null， hash码为 0，也就是说 key为 null的 Entry位于 table[0]的 Entry链上

for (Entry<K, V> e = table[0]; e != null; e = e.next) {

if (e.key == null)

return e.value;

}

return null;

}

public V put(K key, V value) {

if (key == null)

return putForNullKey(value);

//根据 key的 hashCode值计算它的 hash码

int hash = hash(key.hashCode());

//搜索指定 hash值对应 table中的索引值

int i = indexFor(hash, table.length);

for (Entry<K, V> e = table[i]; e != null; e = e.next) {

Object k;

//如果找到指定 key与需要放入的 key相等（ hash值相同，通过 equals比较返回 true）

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

//新的值覆盖旧值

e.value = value;

//这个方法是个空方法，可能是表示个标记，字面意思是表示记录访问

e.recordAccess(this);

//返回旧值

return oldValue;

}

modCount++;

//如果 i处索引处的 Entry为 null，表示此处还没有 Entry

//将 key、 value添加到 i索引处

addEntry(hash, key, value, i);

return null;

}

//key=null的键值对 ,默认存放 table[0]的 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;

}

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);

}

//根据键值移除 key-value映射对象

public V remove(Object key) {

Entry<K, V> e = removeEntryForKey(key);

return (e == null ? null : e.value);

}

final Entry<K, V> removeEntryForKey(Object key) {

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

int i = indexFor(hash, table.length);

Entry<K, V> prev = table[i];

Entry<K, V> e = prev;

while (e != null) {

Entry<K, V> next = e.next;

Object k;

if (e.hash == hash

&& ((k = e.key) == key || (key != null && key.equals(k)))) {

modCount++;

size--;

if (prev == e)

table[i] = next;

else

prev.next = next;

//空方法，表示移除记录

e.recordRemoval(this);

return e;

}

prev = e;

e = next;

}

return e;

}

三、 HashMap 的 hash 算法和 size 大小调整，为什么说 HashMap 此类不保证映射的顺序，特别是它不保证该顺序恒久不变 请看以下分解：

static int hash(int h) {//这里不是很懂，得向他人请教

// 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);

}

/**

* Returns index for hash code h.

// 根据 hash码求的数组小标并返回，当 length为 2的幂时， h & (length-1)等价于 h%(length-1)，这里也就是为什么前面说 table的长度必须是 2的幂

static int indexFor(int h, int length) {

return h & (length - 1);

}

// 调整大小

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 {

//注意这里哈， HashMap不保证顺序恒久不变

//在这里可以找到答案

Entry<K, V> next = e.next;

int i = indexFor(e.hash, newCapacity);

e.next = newTable[i];

newTable[i] = e;

e = next;

} while (e != null);

}

四、 HashMap 与 Set 的关系 ， Set代表一种集合元素无序、集合元素不可重复的集合。如果只考察 HashMap中的 key，不难发现集合中的 key有一个特征：所有的 key不能重复， key之间无序。具备了 Set的特征，所有的 key集合起来组成一个 Set集合。同理所有的 Entry集合起来，也是一个 Set集合。而 value是可以重复的，不能组成一个 Set集合，在 HashMap源代码中提供了 values()方法把 value集合起来组成 Collection集合。

private abstract class HashIterator<E> implements Iterator<E> {

Entry<K, V> next; // next entry to return

int expectedModCount; // For fast-fail

int index; // current slot

Entry<K, V> current; // current entry

HashIterator() {

expectedModCount = modCount;

if (size > 0) { // advance to first entry

Entry[] t = table;

while (index < t.length && (next = t[index++]) == null)

;

}

public final boolean hasNext() {

return next != null;

}

final Entry<K, V> nextEntry() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

Entry<K, V> e = next;

if (e == null)

throw new NoSuchElementException();

if ((next = e.next) == null) {

Entry[] t = table;

while (index < t.length && (next = t[index++]) == null)

;

}

current = e;

return e;

}

public void remove() {

if (current == null)

throw new IllegalStateException();

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

Object k = current.key;

current = null;

HashMap.this.removeEntryForKey(k);

expectedModCount = modCount;

}

private final class ValueIterator extends HashIterator<V> {

public V next() {

return nextEntry().value;

}

private final class KeyIterator extends HashIterator<K> {

public K next() {

return nextEntry().getKey();

}

private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {

public Map.Entry<K, V> next() {

return nextEntry();

}

Iterator<K> newKeyIterator() {

return new KeyIterator();

}

Iterator<V> newValueIterator() {

return new ValueIterator();

}

Iterator<Map.Entry<K, V>> newEntryIterator() {

return new EntryIterator();

}

// Views

private transient Set<Map.Entry<K, V>> entrySet = null;

//把所有的 key集合成 Set集合

public Set<K> keySet() {

Set<K> ks = keySet;

return (ks != null ? ks : (keySet = new KeySet()));

}

private final class KeySet extends AbstractSet<K> {

public Iterator<K> iterator() {

return newKeyIterator();

}

public int size() {

return size;

}

public boolean contains(Object o) {

return containsKey(o);

}

public boolean remove(Object o) {

return HashMap.this.removeEntryForKey(o) != null;

}

public void clear() {

HashMap.this.clear();

}

//把所有的 values集合成 Collection集合

public Collection<V> values() {

Collection<V> vs = values;

return (vs != null ? vs : (values = new Values()));

}

private final class Values extends AbstractCollection<V> {

public Iterator<V> iterator() {

return newValueIterator();

}

public int size() {

return size;

}

public boolean contains(Object o) {

return containsValue(o);

}

public void clear() {

HashMap.this.clear();

}

//把所有的 Entry对象集合成 Set集合

public Set<Map.Entry<K, V>> entrySet() {

return entrySet0();

}

private Set<Map.Entry<K, V>> entrySet0() {

Set<Map.Entry<K, V>> es = entrySet;

return es != null ? es : (entrySet = new EntrySet());

}

private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {

public Iterator<Map.Entry<K, V>> iterator() {

return newEntryIterator();

}

public boolean contains(Object o) {

if (!(o instanceof Map.Entry))

return false;

Map.Entry<K, V> e = (Map.Entry<K, V>) o;

Entry<K, V> candidate = getEntry(e.getKey());

return candidate != null && candidate.equals(e);

}

public boolean remove(Object o) {

return removeMapping(o) != null;

}

public int size() {

return size;

}

public void clear() {

HashMap.this.clear();

}

五、 fail-fast 策略（速错） HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了 map，那么将抛 ConcurrentModificationException，这就是所谓 fail-fast策略（速错），这一策略在源码中的实现是通过 modCount域， modCount顾名思义就是修改次数，对 HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了

private abstract class HashIterator<E> implements Iterator<E> {

Entry<K, V> next; // next entry to return

int expectedModCount; // For fast-fail

int index; // current slot

Entry<K, V> current; // current entry

HashIterator() {

expectedModCount = modCount;

if (size > 0) { // advance to first entry

Entry[] t = table;

while (index < t.length && (next = t[index++]) == null)

;

}

public final boolean hasNext() {

return next != null;

}

final Entry<K, V> nextEntry() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

Entry<K, V> e = next;

if (e == null)

throw new NoSuchElementException();

if ((next = e.next) == null) {

Entry[] t = table;

while (index < t.length && (next = t[index++]) == null)

;

}

current = e;

return e;

}

public void remove() {

if (current == null)

throw new IllegalStateException();

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

Object k = current.key;

current = null;

HashMap.this.removeEntryForKey(k);

expectedModCount = modCount;

}

分享到：

Memcached的使用 | JDK1.6中文版的对HashMap

2012-02-27 10:28
浏览 1325
评论(0)
分类:企业架构
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

JDK1.6中文版的对HashMap

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

JDK1.6中文版的对HashMap

评论

发表评论

相关推荐

idea code

idea

hashmap和hashtable

jdk schedule timer task

synchronized

sdfasdfasdf

syspath

gc---java

JAVA_OPTS

daemon thread

集合的区别总结

ClassLoader

synchronized 规则

JDK1.6中文版的对HashMap

HashMap

Collection

until

Java Thread

最近访客更多访客>>