HashMap源码解析一、构造函数，华为软件开发面试题

this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**

• &＃64;param initialCapacity 初始容量
• &＃64;param loadFactor 负载因子
  */
  public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity <0)
  throw new IllegalArgumentException("Illegal initial capacity: " &＃43;
  initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
  initialCapacity &＃61; MAXIMUM_CAPACITY;
  if (loadFactor <&＃61; 0 || Float.isNaN(loadFactor))
  throw new IllegalArgumentException("Illegal load factor: " &＃43;
  loadFactor);
  this.loadFactor &＃61; loadFactor;
  this.threshold &＃61; tableSizeFor(initialCapacity);
  }

public HashMap(Map m) {
this.loadFactor &＃61; DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
}

HashMap(int initialCapacity, float loadFactor) 构造函数

前两个没什么好讲的&＃xff0c;我们直接看第3个 HashMap(int initialCapacity, float loadFactor)
这里的重点就是 int tableSizeFor(int cap)函数。

tableSizeFor(int cap) 函数

tableSizeFor(int cap) 的作用是返回 大于等于cap 且 最接近cap 的2的幂次方的值

static final int MAXIMUM_CAPACITY &＃61; 1 <<30;
/**

• Returns a power of two size for the given target capacity.
• 返回 大于等于cap 且 最接近cap 的2的幂次方的值
  */
  static final int tableSizeFor(int cap) {
  int n &＃61; cap - 1;
  n |&＃61; n >>> 1;
  n |&＃61; n >>> 2;
  n |&＃61; n >>> 4;
  n |&＃61; n >>> 8;
  n |&＃61; n >>> 16;
  return (n <0) ? 1 : (n >&＃61; MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n &＃43; 1;
  }

我们分步骤解析
一下这个函数&＃xff1a;

1. >>> 无符号右移运算符&＃xff0c;高位用0 填充。如下&＃xff1a;

a &＃61; 1010
a >>> 1 &＃61; 0101

2. | 如果相对应位都是 0&＃xff0c;则结果为 0&＃xff0c;否则为 1。如下&＃xff1a;

a &＃61; 1010
b &＃61; 0011

a | b &＃61; 1011

3. |&＃61; , a |&＃61; b 等同于 a &＃61; a|b。

这时候我们就能看懂 n |&＃61; n >>> 1; 等同于 n &＃61; n | n >>> 1

4. int n &＃61; cap - 1; 是因为如果cap不减1&＃xff0c;当 cap 本来就是2次幂数值&＃xff0c;就会导致返回的结果为 cap*2 。

5. 我们带入一个值看下运行结果&＃xff0c;假设 cap &＃61; 20

static final int tableSizeFor(int cap) {
System.out.println("cap &＃61; "&＃43; Integer.toBinaryString(cap));
int n &＃61; cap - 1;
System.out.println("n &＃61; "&＃43; Integer.toBinaryString(n));
n |&＃61; n >>> 1;
System.out.println("n1 &＃61; "&＃43; Integer.toBinaryString(n));
n |&＃61; n >>> 2;
System.out.println("n2 &＃61; "&＃43; Integer.toBinaryString(n));
n |&＃61; n >>> 4;
System.out.println("n4 &＃61; "&＃43; Integer.toBinaryString(n));
n |&＃61; n >>> 8;
System.out.println("n8 &＃61; "&＃43; Integer.toBinaryString(n));
n |&＃61; n >>> 16;
System.out.println("n16 &＃61; "&＃43; Integer.toBinaryString(n));
System.out.println("n&＃43;1 &＃61; "&＃43; Integer.toBinaryString(n&＃43;1));
return (n <0) ? 1 : (n >&＃61; MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n &＃43; 1;
}

&＃64;Test
public void tableSizeForTest(){
System.out.println(“tableSizeFor:”&＃43; tableSizeFor(20));
}

我这里直接把tableSizeFor(int cap) 拷贝出来&＃xff0c;然后添加了日志。结果如下&＃xff1a;

cap &＃61; 10100
n &＃61; 10011
n1 &＃61; 11011 (10011 | 01001)
n2 &＃61; 11111 (11011 | 01101)
cap) 拷贝出来&＃xff0c;然后添加了日志。结果如下&＃xff1a;

cap &＃61; 10100
n &＃61; 10011
n1 &＃61; 11011 (10011 | 01001)
n2 &＃61; 11111 (11011 | 01101)