数据结构(四)哈希表入门

哈希表(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