day3 哈希表

哈希表

是由数组跟链表组合而成的产物
特点：

• 数组（顺序表）寻址容易
• 链表：插入删除容易
• 哈希表：寻址容易，插入删除也容易的数据结构

例子：HashTable(也叫散列表)

是根据关键码值（key,value）而进行直接访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快访问记录

• 关键码值（key,value）也可以当成是key的hash值，这个映射函数也叫做散列函数

• 装填因子：散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
  α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

• 缺点：扩容需要消耗大量的空间跟性能

• 散列函数与散列表大小 hash冲突的解决方案

• 设计
  拉链法：jdk1.8之前：数组+链表
  jdk1.8之后：数组+红黑树