大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > JavaHashMap分析之一:基本结构

JavaHashMap分析之一:基本结构

关键词:JavaJavaHashMap分析之一:基本结构  阅读(744) 赞(19)

[摘要]本文主要是对JavaHashMap分析之一:基本结构的讲解,希望对大家学习JavaHashMap分析之一:基本结构有所帮助。

  Java的HashMap非常的常用,本篇研究它的实现算法,最后希望计算出内存占用,性能的量化数据,然后得出什么时候使用HashMap,什么时候不能滥用的结论。

  HashMap实际上是一个数组,数组里面的每个元素都是一个链表。每个元素在通过put方法放入HashMap中的时候,要按照如下步骤进行:1.根据该元素自身提供的hashcode计算出散列值,该散列值就是数组的下标2.将新元素放入该数组位置的链表中先来看一下数组的定义:[java] view plaincopy /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table;

  这是一个数组,transient关键字告诉我们它不会参与序列化。既然是一个数组,总有数目上限,也就意味着如果存入HashMap的元素太多,导致数组大小不能够存放所有的链表的时候,数组大小必须要能够调整。所以首先来考察一下数组容量的相关算法。

  第一,Entry是什么类型?

  [java] view plaincopy 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 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());}……

  这是一个HashMap类的内部静态类。实现了Map.Entry接口。接受两个模板参数K和V.key和hash一旦在构造函数中被初始化,就不可改变,并且由于有next的存在,Entry可以构成一个单向链表。

  比较重要的是equals和hashCode方法。代码先列出来,后面再解释。

  第二,初始容量的设定大多数都在下面的构造函数里面。用于指定的initialCapacity不准小于0,也不能超过最大值。并且最终的capicity必须是2的n次方。还有如果使用了无参数的构造函数,默认会创建一个拥有16个元素的数组。

  [java] view plaincopy 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;while (capacity < initialCapacity)

  capacity <<= 1;

  this.loadFactor = loadFactor;threshold = (int)(capacity * loadFactor);table = new Entry[capacity];init();}

  第三,什么时候应该调整数组的大小?

  算法是这样,有一个变量size保存了实际数组已经使用了多少个元素,并且如果size的值达到了变量threshold的值,就必须扩充数组的容量。threshold=capicity*loadFactor.capicity是数组最大的容纳元素个数,loadFactor可以在构造函数中制定,否则采用默认值0.75f.capicity的最大值是1<<30(也就是2的30次方,1073741824)。由此我们可以看到HashMap最多存放10亿多个链表。

  第四,如何调整数组大小?

  答案是2倍,很像C++里面的vector的分配策略。

  [java] view plaincopy 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);}

  第五,为什么数组大小必须是2的倍数?

  在后面介绍散列值算法的时候会回答。



相关评论