Word文档中的单词拼写检查功能是如何实现的

散列思想

散列表用的是数组支持按照下标随机访问数据的特性
散列表其实是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表

image.png
这种key value映射的方式叫散列函数，而散列函数计算得到的值就叫作散列值或哈希值

散列函数

散列函数是一个函数，可以把它定义成hash，其中key表示元素的键值，hash的值表示经过散列函数计算得到的散列值。

  1. 散列函数计算得到的散列值是一个非负整数；
  2. 如果key1 = key2，那hash(key1) == hash(key2)
  3. 如果key1 ≠ key2，那hash(key1) ≠ hash(key2)

散列冲突

再好的散列函数也无法避免散列冲突。
常用的散列冲突解决方法有两类，开放寻址法和链表法

上面第三点，在真实情况下，想要找到一个不同的key对应的散列值都不一样的散列函数，几乎不可能。

开放寻址法

核心思想，如果出现了散列冲突，就重新探测一个空闲位置，将其插入。

散列表跟数组一样，不仅支持插入、查找操作，还支持删除操作。

链表法

image.png