哈希表

一 哈希表定义

哈希表的引入：

​ 链表和树的查找的共同特点是：通过关键字值与给定值进行比较，确定位置，效率取决于比较次数，如： 顺序表根据索引查很快，但根据内容查很慢

理想的方法是：不需要比较，根据给定值直接定位存储的位置

这样需要记录存储位置与该记录的关键字建立关系，使每个记录的关键字与一个存储位置向对应

hashtable有称散列表

特点：快

结构：有多种

最流行最容易理解的：顺序表+链表

主结构：顺序表

每个顺序表的节点单独引出一个链表

二 哈希表的操作

2.1 哈希表添加元素

1：计算哈希码（调用hashCode()）,结果是一个int值，（整数的哈希吗取自身）

2：计算哈希表中的存储位置y=k(x)=x%11 x:哈希吗，y：在哈希表的存储位置，%取余数

3：存入哈希表

1:一次添加成功
2：多次添加成功（出现了冲突，调用equals()和对应的链表的元素进行比较，比较到最后，都是false，创建新节点，存储数据，并加入链表末尾）
3：不添加（出现了冲突，调用equals()和对应的链表的元素进行比较，经过一次或多次，结果为true。表名重复，不添加）

特点： 添加快（不考虑哈希冲突），数据唯一， 数据无序

2.2 哈希表查询

查询与插入流程基本一致

1: 一次找到
2：多次找到
3：找不到

查询数据块，删除快，更新数据（若是更新后影响哈希吗，比较繁琐，需要删除在添加）

2.3 哈希表减少冲突

1: 哈希表的长度和表中的记录数的比例--装填因子
若是哈希表的空间远大于实际存储的记录数吗，造成空间浪费，选取小了，容易冲突。实际中，装填因子=记录数/哈希表长度，一般情况下，装填因子去经验值0.5
2：哈希函数的选择
 直接定址法  平方取中法 折叠法 除留取余法 查资料
3：处理冲突的方法
链地址法 开放地址法 在散列法  建立公共溢出区

java中的hashmap,hashset等

1：jdk1.7及其以前hashmap的底层就是一个table数组+链表实现的,在1.8有变化，当链表的长度大与8时，不在采用链表，而是用了红黑树，这样主要是查询的复杂度上，链表为o(n),红黑树为o(logn)，若是冲突过多，并且超过8，采用红黑树提高效率
2：hashset的底层是hashmap
3：hashmap的装填因子为0.75，默认数组长度为16
4：treeset和treemap 底层用的红黑树
5：hashset，hashmap底层是哈希表