Java HashMap深入分析

jopen 10年前

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。

HashMap 的实例有两个参数...

hash存储过程:
初始化:
1: 首先初始化hash结构, 初始化桶的个数和加载因子.
put(k, v):
1: 通过k的hashcode值再hash的得到h, 再和桶的长度进行indexFor(int h, int length),得出桶的index.
2: 相当于在桶的中寻找出合适的位置.
3: 在这个位置放下这个对象:table[i] = Entry(k, v), Entry实际上是一个链表
4: 将数据放在链表的一个位置. table[i].next =new Entry(k, v, oldValue).
5: 如果数据增加到临界值(初始大小*加载因子), 则需要重新创建以前2倍大小的桶(new_table=2*table).
6: 然后将table数据再拷贝到newtable中, 当然拷贝的只是table的索引.
get(k):
1: 通过k的hashcode值再hash的得到h和桶的长度(length). 再进行indexFor(int h, int length),得出桶的index.
2: 取出桶中的数据Entry,由于Entry是一个链表所以需要遍历出k的hash值和key都是相等的数据.

//HashMap  public HashMap() {      //即上文说的加载因子(默认0.75)          this.loadFactor = DEFAULT_LOAD_FACTOR;          //默认大小(12 = 16 * 0.75)          threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);          //初始化桶的个数          table = new Entry[DEFAULT_INITIAL_CAPACITY];          init();      }        //put方法:  public V put(K key, V value) {      if (key == null)          return putForNullKey(value);          //hashCode=> hash      int hash = hash(key.hashCode());      //hash => index      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;  }     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)      //如果容量过大应该重建table结构.          resize(2 * table.length);  }    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);  }    //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;  }