你的位置:首页 > Java教程

[Java教程]java HashMap


HashMap 的性能因子

1. 容量:表示桶位的数量。

2. 初始容量: 表在创建是所拥有的桶位数。

  •   如果你知道将要在HashMap存储多少项,创建一个初始容量合适的HashMap将可以避免自动再散列的开销
  /**   * The default initial capacity - MUST be a power of two.   */  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认大小

3. 尺寸: 表中当前存储的项数。

 

4. 负载因子:尺寸/容量。 负载因子小的表冲突的可能性小,插入和查找的速度也相对较快(但会减慢使用迭代器进行遍历的过程)。HashMap和HashSet都具有允许你指定负载因子的构造器,表示当负载情况达到负载因子的水平时,容器将自动增加容量。实现方法是使容量加倍,并将现有对象分配到新的桶位集中。

  /**   * The load factor used when none specified in constructor.   */  static final float DEFAULT_LOAD_FACTOR = 0.75f;

 

HashMap构造器

创建HashMap对象时,无论调用哪个构造器,最终都会调用

HashMap(int initialCapacity, float loadFactor), initialCapacity为初始容量, loadFactor为负载因子
/**   * Constructs an empty <tt>HashMap</tt> with the specified initial   * capacity and load factor.   *   * @param initialCapacity the initial capacity   * @param loadFactor   the load factor   * @throws IllegalArgumentException if the initial capacity is negative   *     or the load factor is nonpositive   */  public HashMap(int initialCapacity, float loadFactor) {    if (initialCapacity < 0)      throw new IllegalArgumentException("Illegal initial capacity: " +          initialCapacity);    if (initialCapacity > MAXIMUM_CAPACITY) // MAXIMUM_CAPACITY为最大容量      initialCapacity = MAXIMUM_CAPACITY;    if (loadFactor <= 0 || Float.isNaN(loadFactor))      throw new IllegalArgumentException("Illegal load factor: " +          loadFactor);    this.loadFactor = loadFactor;    this.threshold = tableSizeFor(initialCapacity); // tableSizeFor(initialCapacity) 会返回 x, x 满足 x = 2^n 且 x >= initialCapacity)  }

 

来看看tableSizeFor的实现(个人绝对想不到这么高大上的方法)

  /**   * Returns a power of two size for the given target capacity.   */  static final int tableSizeFor(int cap) {    int n = cap - 1; //这里是因为考虑到cap为2的整数次幂的情况    //1. 假设此时n的二进制最高位1在第i位(最低位为第0位)    n |= n >>> 1;    //2. 此时n的二进制第i, i-1位都为1    n |= n >>> 2;    //3. 此时n的二进制第i, i-1, i-2, i-3位都为1    n |= n >>> 4;     //4. 此时n的二进制第i, i-1, i-2, i-3, i-4, i-5, i-6, i-7位都为1(当然,严谨点应该再假设i>7)    n |= n >>> 8;    //5.---------    n |= n >>> 16;    //6.---------    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;  }