**LinkedList**:
单向链表:
存储一个元素,指向下一个元素的引用地址值
双向链表:
存储一个元素,指向下一个元素的引用地址值和指向上一个元素的引用地址值
LinkedList采用的是双向链表;
**哈希算法**:
通过key-value的格式,让key和value存在一种关系的算法,比如数组中的索引和元素的关系
**哈希表**:
一种数据结构;
用于hash算法存储的关系式的数据结构
**哈希冲突**:
两个不同的地理值通过hash算法产生相同的key
**jdk1.8之前Hashmap**:
组成:
链表散列 //又称为数组+链表
特点:
通过key的扰动函数(hash方法)来判断键值对的键是否存在,如果键中的key和hashcode相等,则覆盖,不相等则通过拉链法解决冲突;
对比jdk1.7的hash算法,jdk1.8的hash算法优化了一些,主要是jdk1.7的扰动函数动用了四次;
**jdk1.8之后HashMap**:
组成:
数组+链表+红黑树
特点:
链表法:
将hash冲突的键值对存入数组中元素的链表(每个数组中的元素其实就是一个链表);
当链表的阈值(默认为8即长度)修改为红黑树结构,便于链表的查询
**属性**:
初始化容量:
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16
填充因子:
static final float DEFAULT_LOAD_FACTOR = 0.75f;
桶节点(链表长度大于设置的值修改为红黑树结构):
static final int TREEIFY_THRESHOLD = 8;
加载因子:
final float loadFactor;
概念:
entry数组jdk-1.8之后又称为node数组,加载因子决定这个数组的疏密度,利用率,效率,趋近于0的时候,数组中存放的数据就小,趋近于1的时候数组中存放的数据就大;
默认容量是16,默认的加载因子是0.75则容器在长度为16*0.75=12的时候则会进行扩容;
临界值: ****
int threshold;
概念:
当实际大小超过(容量*填充因子)临界值时,则进行扩容
核心方法:
构造方法:
四个:
HashMap() //默认的有参构造
HashMap(Map<? extends K, ? extends V> m) //包含一个map的构造方法
HashMap(int initialCapacity) //指定容量的构造函数
HashMap(int initialCapacity, float loadFactor) //指定加载因子和容量的构造方法
核心方法:
hash()
概念:
将传进来的key计算出hashcode值,在对hashcode值进行高16 ^ 低16 运算,作为node数组的下标;
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
初始化容量:
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
这里的1>>4 其实使用位运算是效率高
put()
首先判断传进来的key-value作为一个node数组;
判断是否需要扩容,resize() //要么初始化,要么扩容
初始化后,采用if ((p = tab[i = (n - 1) & hash]) == null)
n-1表示要填充的node[] 数组不能越界,并且计算出hash值
get()
resize()
进行少使用,resize()非常消耗资源
面试题:
为什么hashmap中的容量是2的次冥?
答:
因为是2的次冥,数组的散列就越大,碰撞几率就变小. |
|
收藏
淘帖
踩
