哈希表示用来实现快速插入和快速查找的数据结构
Design a hash table
- 哈希表的原则就是用一个哈希函数来把键映射到存储槽
- 设计哈希表时的一个关键因素是选择哈希函数，哈希函数应该尽可能让key到存储槽的映射均匀分布
- 另一个关键因素是冲突解决，大部分哈希表都做不到键与存储槽之间完美的一一映射，因此要处理在同一个存储槽中的键
- 编程语言内置的哈希表，插入和查找操作都是O(1)时间复杂度，但如果太多键在同一个存储槽中，那么这些键会以高度平衡二叉树来存储，平均情况下，插入和查找操作都还是O(1)复杂度，但最坏情况下两者都会变为O(logN)
Practical application - hash set
- 通常，一个hash set一般用来检查一个元素是否出现过了
Practical application - hash map
- Java中遍历hash map时，用keySet()就可以，不过entrySet()似乎更好，能少一次循环
- hash map的一种使用场景是在我们可以使用hash set时需要比Key更多的信息，所以用hash map来建立key和其它信息的映射
- hash map的另一种使用场景是“按键汇总所有信息”，其实不太好区分场景一和场景二的区别，好像就是场景二更侧重汇总所有信息来判断，而场景一是一旦有需要的信息就结束了
- 处理场景二类问题的关键在于遇到已经存在的键时如何处理
Practical application - design the key
- 有时候键的选择并不简单直接，需要自己设计。设计一个键就是自己去建立一个键到一组值的映射，要保证所有同组的值应该被映射到同一个键，所有不同组的值应该被映射到不同的键
- Java中char类型用单引号，字符串用双引号
总结：在经常需要查找和插入时，哈希表是一个很好的选择
