哈希表(Hash table)
哈希表,也叫散列表,是根据关键代码(key,value)而进行访问的数据结构,它通过把关键码映射到表中一个位置来访问记录,以加快查找的速度.
关键码值(key,vale)也可以当成是key的hash值,这个映射函数叫做散列函数
存放记录的数组叫做散列表
特点
- 数组(顺序表):寻址容易
- 链表:插入与删除容易
- 哈希表:寻址容易,插入删除也容易的数据结构,缺点:扩容会消耗大量的空间和性能
应用点:在数组大小变话可能性比较少的情况下(电话号码,字典,点歌系统,QQ,微信好友)
1.hashtable例子
- Key : {14, 19, 5, 7, 21, 1, 13, 0, 18}
- 散列表: 大小为13 的数组 a[13];
- 散列函数: f(x) = x mod 13;
- hashtable需要自定义的内容:散列函数与散列表大小
hash 冲突的解决方案 - 装填因子：为什么需要这个值？因为数据越接近数组最大值，可能产生冲突的情况就越多,例如装填因子是9/13,放满9个后就会扩容(hashmap的装填因子是0.75),因为数据越接近数组最大值,可能产生冲突的情况就越来越多,扩容后散列函数会重新变,散列表中的值会重新计算,所有哈希表扩容会消费大量的空间和性能
-
image
2. 拉链法
jdk1.8以前,采用数组+链表
image
但当数据量特别大的时候,每个链表上的数据量也会特别大
,右移1.8以后采用当链表长度超过阈值,就转换红黑树
image
俩中方法查找的执行次数
image
网友评论