集合分为单列集合和双列集合
我们常用的是ArrayList和HashMap
ArrayList底层是数组,默认长度为0;当添加第一个元素时,长度变为10,扩容机制是当数组存满时,还要继续添加元素,就会创建一个新的数组,容量是之前数组的1.5倍,并把之前元素复制进新数组。
HashMap1.7之前底层是数组+链表,1.8之后是数组+链表+红黑树,底层重写了hashcode和equals方法,先计算hash值,hash值会根据hash函数计算出索引值,存入指定位置,如果位置上没有,存入,如果有比较equals,如果相同,新值替换旧值,如果不同,就挂下面,链表长度大于等于8,转为红黑树,小于等于6,转成链表。扩容机制,默认是16,加载因子0.75,每次长度乘2。
HashMap的主干是一个Entry数组。 Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。 Entry是hashmap中的静态内部类
HashMap中关键属性
transient Entry[] table; // 存储元素的实体数组
transient int size;// 存放元素的个数
int threshold; // 临界值 当实际大小超过临界值时,会进行扩容threshold = 加载因子*容量
final float loadFactor; // 加载因子
transient int modCount;// 被修改的次数
HashTable和concurrenthashmap线程安全,hashtable所有的方法都是synchronized修饰的 concurrenthashmap1.7之后是CAS+synchronized,所以是线程安全的。
hash碰撞冲突:hashCode()的方法是为了产生不同的hash值,但是当两个对象的hash一样时,就发生了碰撞冲突
我们常用的解决方法有四种:
开放地址法: 基本思想:当发生地址冲突的时候,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止 所用公式 Hi(key) = [H(key) + di]mod m;其中i = 1、2、3…k(k<m-1),H(key)为关键字key的直接hash地址;M为hash表的长度; di为再次探测时的地址增量;根据di的不同取法,有不同的称呼; 线性探测再散列:di = 1、2、3、4…k (k<m-1) 二次探测再散列:di = 12,-12,22,-22…k2,-k2 (k<=m/2) 伪随机再散列:di = 伪随机数
再hash法: 当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。 缺点:计算时间增加。 比如上面第一次按照姓首字母进行哈希,如果产生冲突可以按照姓字母首字母第二位进行哈希,再冲突,第三位,直到不冲突为止;
拉链法: 在HashMap中 就是使用拉链法 来解决hash冲突的问题的; 将所有关键字为同义词的记录存储在同一线性链表中。 优点:
缺点: 指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。
建立公共溢出区: 建立公共溢出区的基本思想是:假设哈希函数的值域是[1,m-1],则设向量HashTable[0…m-1]为基本表,每个分量存放一个记录,另外设向量OverTable[0…v]为溢出表,所有关键字和基本表中关键字为同义词的记录,不管它们由哈希函数得到的哈希地址是什么,一旦发生冲突,都填入溢出表。
1、hash(key),取key的hashcode进行高位运算,返回hash值 2、如果hash数组为空,直接resize() 3、对hash进行取模运算计算,得到key-value在数组中的存储位置i (1)如果table[i] == null,直接插入Node<key,value> (2)如果table[i] != null,判断是否为红黑树p instanceof TreeNode。 (3)如果是红黑树,则判断TreeNode是否已存在,如果存在则直接返回oldnode并更新;不存在则直接插入红黑树,++size,超出threshold容量就扩容 (4)如果是链表,则判断Node是否已存在,如果存在则直接返回oldnode并更新;不存在则直接插入链表尾部,判断链表长度,如果大于8则转为红黑树存储,++size,超出threshold容量就扩容
1.8之前是头插法,1.8之后是尾插法
public V put(K key, V value) {
// 如果table数组为空数组{},进行数组填充(为table分配实际内存空间),入参为threshold,
// 此时threshold为initialCapacity 默认是1<<4(24=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果key为null,存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);// 对key的hashcode进一步计算,确保散列均匀
int i = indexFor(hash, table.length);// 获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
// 如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value
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++;// 保证并发访问时,若HashMap内部结构发生变化,快速响应失败
addEntry(hash, key, value, i);// 新增一个entry
return null;
}
HashMap
HashMap的实现原理: 首先有一个每个元素都是链表(可能表述不准确)的数组,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。 当链表数组的容量超过初始容量的0.75时,再散列将链表数组扩大2倍,把原链表数组的搬移到新的数组中