哈希表
通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
散列函数(映射函数)
满足计算简单和分布均匀的两大原则
五大方法
1. 直接定址法:(像利用数组下标对照着定位放) -- 计算简单但是分布可能不均匀
2. 数字分析法:(事先知道数据分布) -- 比如电话号码/身份证号码只需要考虑后几位存放问题
3. 平方取中法:(将所存的数字平方之后取最中间的位) -- 比如17*17=289 放到数组下标为8的位置(会冲突)
4. 取余法:(将所存的数字取余数) -- 比如17%10=7放到数组下标为7的位置(会冲突)
5. 随机数法:(将所存的数字random()方法随便放) --不建议使用(随便放进去的不好取出来)散列冲突的解决方案
两大方法
1. 开放地址法
1.1 线性探测法 -- 有冲突的就 依次向后找空位放
1.2 二次探测法 -- 有冲突的就 按照1的平方 2的平方 ..找空位放
1.3 再哈希法 -- 使用两个散列函数存放
2. 链地址法(HashMap底层)
数组+链表的形式:(在数组下标对应的数组相当于建立一个链表，把符合相应条件的按照顺序指向)
