对java集合相关的一些基础总结，具体每个类可以通过IDE查看源码，这里会借助一些源码来说明，但是不进行源码全面分析
注：源码基于jdk1.8版本
HashMap
HashMap是平时很常用的，也是各公司面试笔试都会涉及到的
平时使用的时候大概是这样的
Map myMap = new HashMap();
用的多，其基本构造，我们应该了解一下。
下面我们对HashMap结合源码进行一个简单的分析，如果不想看分析过程，可以拉到最下面查看总结。
HashMap类的声明是这样的
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap的大致结构是这样的
HashMap大致结构.png
（手绘的，粗糙了些，见谅）
大致就是这个样子
纵向的是一个类似于数组的结构，横向的类似于链表
纵向的每一个，1,2,3,4,5等等，这个有个名称bucket 一般翻译为桶
HashMap容量和扩容
- 默认创建的
HashMap的大小是16，就是说上面那个图在默认情况下，纵向有16个格子（16个桶）。在源码中是这样定义的
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
其中的1<<4指的是二进制的1，往左边移动4位，移过的地方补0，1就变成了二进制的10000，这个就是十进制的16
如果是1被左移的话，可以理解为2^n，就是2的多少次方
在创建的时候，我们可以给构造函数传入一个大小，来指定HashMap的初始大小
Map myMap = new HashMap(30);
我们这里传入的是30，是不是就是有30个桶的HashMap呢?
不是。
跟着源码过去看看，对传入的容量大小，有个计算过程：
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
其中的n>>>1表示将n的二进制数，右移1位，高位补0，比如 n=5，二进制就是0101, 5>>>1之后是0010
n |= n>>>1 就是 n = n|(n>>>1)
其中的 |，与运算符，也是二进制层面的，计算规则就是
1|0 = 1
1|1 = 1
0|0 = 0
依然用n=5举例，我们来计算 n |= n>>>1
首先5的二进制数字是101， 5>>>1=0010
那么101|10是多少呢，按位与：
101
010
结果 111
按位与的结果是 111
好了，有了这个计算基础，可以自行举例通过上面的算法计算出的结果
这个算法的作用就是找到大于等于传进去的容量数值的最小的2的幂
什么意思呢
比如你输入的是30，那么大于等于30的最小的2的幂是2^5,32
所以，输入进去的容量，不一定是最终HashMap的容量
然后，最大容量：
static final int MAXIMUM_CAPACITY = 1 << 30;
- 在这类集合类型的类中，有一个概念，负载因子，
HashMap的负载因子默认为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
意思就是，16*0.75 = 12，在有12个桶装了东西之后，就需要扩容，这里涉及两个问题，第一，扩容的时机，第二，扩容的机制
首先，扩容的时机，不同的版本，时机不同，可以从put源码里看到，具体代码不贴了，有IDE的同学顺手就能找到。
在jdk1.8里面，put 调用的是 putVal，这个方法最后，在将元素添加完成后，有一个操作
if (++size > threshold)
resize();
这里的 threshold 不是上面我们计算出来的实际容量，是putVal刚开始的resize()方法中乘以负载因子的一个容量
实际意思就是，每次put执行之后，会对当前size增加1，然后和 容量*负载因子 进行比较，提前进行扩容操作
然后，在jdk1.7里面，扩容是在每次往里put之前执行的，源码我们下面讲解put的时候回分析。
所以，如果有面试官提问，HashMap的扩容时机，有可能是挖了一个坑，看你对版本变更是否熟悉。
然后，扩容的机制，在resize()中，主要就是一句
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
newCap = oldCap << 1 这个就是计算新的容量，<<1，左移1位，就是乘以2的意思。
新的容量是旧容量的两倍。
上面讲的都是桶的扩容，比如默认是16个桶，负载因子是0.75，有12个桶装了东西之后，就会触发扩容，单个桶里装了多少，不计算在内。
HashMap添加数据
不确定是从哪个版本开始，HashMap的初始化是在第一次put的时候才进行，在没有put数据的时候，没有进行初始化，以此节约内存。
简单分析一下添加数据的过程
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
我们put了k v之后，实际调用了putVal(hash(key), key, value, false, true)，第一个参数就是hash(key)，这个是计算key的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
整个计算过程，没有兴趣的话不用深究，但从这里至少可以看出，HashMap是可以接受 key为null 的，这个是HashMap的特性之一。
如果key为null，那么它的hash值就是0，如果key不为null，那么通过后边的算法给计算一个出来。
接下来就是putVal的源码，在1.8里，这个代码写的有点复杂，看着头疼，我们可以回头去看看1.7里面的put过程，1.8只是进行了一些优化，大致过程没有变。
下面是jdk1.7里面的put的源码。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
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;
}
这个代码看着就亲切多了。。。
部分同学可能不喜欢加注解的分析方式，所以这里我就分开一段一段的解析。
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
这一段就是判断整个HashMap是否为空，如果为空，则初始化
if (key == null)
return putForNullKey(value);
HashMap允许key为null，那么key是null的时候，直接调用 putForNullKey 处理
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;
}
从这里可以看出来，key为null的话，直接存入table[0]，如果已经有一个key为null的值存在了，那么替换掉原来的value，将新的value放进去。
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;
}
}
这一段是查找是否已经有一个相同的key存在了
比较两个key是否相同的过程，可以关注一下
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
第一，hash值必须相等，hash怎么算出来的，可以自己去看看代码
第二，key值相等，或者equal
满足这两个条件，就认为是相同的key，用新的value，替换旧的value。
最后，对于新的值，使用
addEntry(hash, key, value, i);
这种方式插入进去，这个方法的源码
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
可以看到，在jdk1.7版本里，扩容是在添加新数据的时候发生的，原容量x2进行扩容
然后 createEntry就是创建一个新的节点
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
从源码可以看出，这个桶原来的第一个值，被挪到后边去了，看看Entry的结构
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
第四个参数 e ，就是next
所以，如果当前桶已经有值了，新增加的值是添加到开头的。
对HashMap的基础总结大概就这些，后边有新的内容在添加。
总结
HashMap 的默认初识容量为 16，负载因子为 0.75 ，扩容机制是 当前容量x2
扩容时机，不同版本不一样，1.7版本是添加新内容是检测扩容，1.8版本是添加完成后检测
那么，我们在使用的时候，为了避免频繁扩容带来的消耗，对HashMap的初始容量就需要结合实际情况计算一下，比如，当前应用，放入HashMap的成员最多300个，那么，300/0.75=400,那我们对于HashMap的初始大小，至少需要400.
非线程安全，整个源码里没有使用同步机制
允许key为null，允许value为null。
所以，这里有个问题，如果我们使用get获取value值时，如果得到的时value，无法确定这个null是因为HashMap里没有这个key返回的null还是value值就是null，这个时候需要用containsKey先判断一次。这样就比较麻烦了，一般我们不往里边存null。
网友评论