一、哈希表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的特点：
二、哈希函数
哈希函数（Hash Function），也称为散列函数，给定一个输入x，它会算出相应的输出H(x)。哈希函数的主要特征是：https://www.jianshu.com/p/bba9b61b80e7
- 输入x可以是任意长度的字符串
- 输出结果即H(x)的长度是固定的
- 计算 H(x) 的过程是高效的（对于长度为 n 的字符串 x ，计算出 H(x) 的时间复杂度应为 O(n) ）
开放定址法：依靠数组中的空位解决碰撞冲突
再哈希法：使用多个哈希函数，第一个冲突时，使用第二个哈希函数，知道不冲突为止；
哈希函数总结：上述设计方式都是转化成整型处理，并不是唯一的方法，
原则：
1.一致性：如果a == b,则hash(a) == hash(b)
2.高效性：计算高效简便
3.均匀性：哈希值均匀分布
常用的字符串哈希函数（转）
| Hash函数 | 数据1 | 数据2 | 数据3 | 数据4 | 数据1得分 | 数据2得分 | 数据3得分 | 数据4得分 | 平均分 |
| BKDRHash | 2 | 0 | 4774 | 481 | 96.55 | 100 | 90.95 | 82.05 | 92.64 |
| APHash | 2 | 3 | 4754 | 493 | 96.55 | 88.46 | 100 | 51.28 | 86.28 |
| DJBHash | 2 | 2 | 4975 | 474 | 96.55 | 92.31 | 0 | 100 | 83.43 |
| JSHash | 1 | 4 | 4761 | 506 | 100 | 84.62 | 96.83 | 17.95 | 81.94 |
| RSHash | 1 | 0 | 4861 | 505 | 100 | 100 | 51.58 | 20.51 | 75.96 |
| SDBMHash | 3 | 2 | 4849 | 504 | 93.1 | 92.31 | 57.01 | 23.08 | 72.41 |
| PJWHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
| ELFHash | 30 | 26 | 4878 | 513 | 0 | 0 | 43.89 | 0 | 21.95 |
三、装载因子
装载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小. 因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷。
HashMap默认的加载因子是0.75，最大容量是16，因此可以得出HashMap的默认容量是：0.75*16=12。用户可以自定义最大容量和加载因子。
原文：https://www.cnblogs.com/nxnslc-blog/p/14131075.html