直接地址表
直接地址表是一种数据结构，具有使用数组将记录映射到其相应键的功能。 在直接地址表中，将记录的键值直接用作索引来放置记录。 它们有助于快速搜索，插入和删除操作。
我们可以使用以下示例来理解该概念。 我们创建一个大小等于最大值加一的数组（假定索引从 0 开始），然后将值用作索引。 例如，在下图中，键 21 直接用作索引。
优势：
-
在
O(1)时间中搜索：直接地址表使用的数组是随机访问数据结构，因此，键值（也是数组的索引）可以很容易地用于在其中搜索记录O(1)时间。 -
在
O(1)时间中插入：我们可以轻松地在O(1)时间将元素插入数组。 同样的事情也出现在直接地址表中。 -
在
O(1)时间中删除：元素的删除在数组中需要O(1)时间。 同样，要删除直接地址表中的元素，我们需要O(1)时间。
局限性：
-
事先知道最大键值。
-
仅当最大值非常小时才实用。
-
如果总记录和最大值之间存在显着差异，则会导致内存空间浪费。
哈希可以克服直接地址表的这些限制。
如何处理碰撞？
可以像哈希一样处理冲突。 我们可以使用链接或开放式寻址来处理冲突。 与哈希的唯一区别在于，我们不使用哈希函数来查找索引。 我们宁愿直接使用值作为索引。
版权属于：月萌API www.moonapi.com，转载请注明出处
