散列表

散列表

• 认识
  散列表 是 字典（键 、值对）的一种实现方式。每次在字典中获取一个值，都需要重复遍历字典，如果用散列表，字典中每个key都对应一个位置，从而不需要遍历。

以电子邮件地址簿为例，每个名字（key）对应一个邮件地址，用散列函数计算每个key在散列表中的位置（这里使用key的所有字符的ASCII码值相加），如图：

image.png

• 问题：
  1、问：这个散列值 跟 散列表 在内存中有固定的结构关系么？
  答：没有，散列表实际结构不需要是数组，也可以是列表、二叉树之类的，散列表的本质是从key直接计算出value的位置。
  问：明白了，就是这个索引可能是value的内存地址，可能是数组的一个下表，也可能是二叉树中的一个节点值？
  答：是的，我认为如此，比如，也可以是个分段列表，0-1000在第一块，1001-2000在第二块，这样。
  答案由窦老师提供
  2、有两个字典，分别存有 100 条数据和 10000 条数据，如果用一个不存在的 key 去查找数据，在哪个字典中速度更快？
  答案链接：http://ios.jobbole.com/87716/
  3、装有字符的数组，字符值都在ASCII表中，求数组中每个字符出现的次数？
  答题思路：新建散列表，索引为字符的ascii数值，值为出现数组下表，装有字符的数组遍历

• iOS哈希表：

  哈希表（hash table,也叫散列表），是根据关键码值（key value）而进行直接访问的数据结构。也就是说，它通过把关键码值映射到表中的一个位置来访问记录，以加快查找速度。这个映射函数叫散列函数，存放记录的数组叫做散列表。
  哈希表hash table(key value)就是把key 通过一个固定的算法函数即所谓哈希函数转换为一个整形数字即哈希值，然后就将该数字对数组的长度取余，取余结果当做数组的下标，将value存储在以改数字为下表的数组空间里。而当使用哈希表进行查询的时候，就是在此将哈希函数将key转换为对应数组下标，并定位到该空间获取value,如此一来，就可以充分利用数组定位性能进行数据定位

代码实现参见：https://draveness.me/hashtable

问题：哈希表与NSDictionary的区别与联系
NSDictionary是使用hash表来实现key和value之间的映射和存储的，hash函数设计的好坏直接影响数据的查找访问效率，数据在hash表中分布越均匀，其访问效率越高。而在Objective-C中，通常都是利用NSString 来作为键值，其内部使用的hash函数也是通过使用 NSString对象作为键值来保证数据的各个节点在hash表中均匀分布。

NSDictionary实现原理：https://blog.csdn.net/linshaolie/article/details/41494303
散列表原理：https://segmentfault.com/a/1190000008556414
哈希表 概念 https://www.jianshu.com/p/88dfc8f405ab