常见概念

随机访问

随机访问（Random Access）是指在数据结构中，可以在常数时间内（O(1)）直接访问任意一个元素，而不需要从头开始遍历数据结构。数组（Array）是支持随机访问的典型数据结构，因为可以通过索引(数据地址+偏移量)直接访问任意位置的元素。

在支持随机访问的数据结构中，元素的存储位置是连续的，这使得通过计算偏移量来直接定位元素成为可能。相比之下，链表（Linked List）不支持随机访问，因为访问某个元素需要从头开始逐个遍历，时间复杂度为 O(n)。

随机访问的优势在于其高效性，特别是在需要频繁访问或修改特定位置的元素时。然而，这种高效性通常是以牺牲插入和删除操作的效率为代价的，因为在数组中插入或删除元素可能需要移动大量数据。

哈希表

哈希表就是键值对吗

哈希表（Hash Table）确实是基于键值对（key-value pair）的一种数据结构。它通过一个哈希函数将键映射到一个数组中的位置，以便快速查找对应的值。以下是哈希表的一些关键特性：

  1. 键值对存储：哈希表中的每个元素都是一个键值对。键用于标识数据，值是与该键相关联的数据。

  2. 快速查找：通过哈希函数，哈希表可以在平均情况下以常数时间复杂度（O(1)）进行查找、插入和删除操作。

  3. 哈希冲突：由于不同的键可能映射到相同的哈希值，哈希表需要处理冲突。常见的冲突解决方法包括链地址法（使用链表存储冲突的元素）和开放地址法（在数组中寻找下一个空闲位置）。

  4. 动态调整：为了保持高效性，哈希表通常会在负载因子（已存储元素数量与数组大小的比值）超过某个阈值时进行扩展和重哈希。

因此，哈希表不仅仅是键值对的简单集合，它还包含了用于高效存储和检索的机制。

哈希冲突

哈希冲突（Hash Collision）是指在哈希表中，不同的键通过哈希函数映射到相同的哈希值或数组位置的情况。由于哈希表的核心是通过哈希函数将键映射到数组中的位置，因此冲突是不可避免的。处理哈希冲突的方法主要有以下几种：

  1. 链地址法（Separate Chaining）：

    • 在每个数组位置存储一个链表（或其他数据结构），所有映射到同一位置的元素都存储在这个链表中。
    • 当发生冲突时，将新元素添加到链表中。
    • 查找时，需要遍历链表来查找目标元素。

  2. 开放地址法（Open Addressing）：

    • 当发生冲突时，寻找数组中的下一个空闲位置来存储元素。
    • 常见的开放地址法策略包括线性探测（Linear Probing）、二次探测（Quadratic Probing）和双重哈希（Double Hashing）。

  3. 再哈希（Rehashing）：

    • 当哈希表的负载因子超过某个阈值时，创建一个更大的哈希表，并将所有元素重新哈希到新的表中(扩容)。
    • 这可以减少冲突的发生频率。

扩容哈希表

负载因子定义为哈希表中元素数量除以桶数量，反映了哈希冲突的严重程度，常用作触发哈希表扩容的条件。

简单粗暴，但是效率低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。

改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。

  • 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。
  • 哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。

链式地址的局限性

  • 占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间。
  • 查询效率降低：因为需要线性遍历链表来查找对应元素。

值得注意的是，当链表很长时，查询效率 O(n) 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而将查询操作的时间复杂度优化至 O(logn)。

开放寻址的局限性

  • 线性探测容易产生“聚集现象”。数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。
  • 负载因子不能太大，否则会降低查询效率。
  • 删除元素比较麻烦，不能直接删除，需要惰性删除(lazy delete)。这是因为删除元素会在数组内产生一个空桶 None ，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在。
    • 惰性删除: 不直接从哈希表中移除元素，而是利用一个常量 TOMBSTONE 来标记这个桶。在该机制下，None 和 TOMBSTONE 都代表空桶，都可以放置键值对。但不同的是，线性探测到 TOMBSTONE 时应该继续遍历，因为其之下可能还存在键值对。

请注意，开放寻址（线性探测、平方探测和多次哈希）哈希表都存在“不能直接删除元素”的问题。

怎么理解哈希的输入空间通常远大于输出空间（数组长度）

哈希函数的输入空间通常远大于输出空间的原因在于，哈希函数需要将一个非常大的输入集合（如所有可能的字符串或整数）映射到一个相对较小的输出集合（如哈希表的数组索引）。这种映射过程不可避免地会导致哈希冲突，因为多个不同的输入可能会被映射到相同的输出值。

理解这一点的几个关键点

  1. 输入空间的广泛性：

    • 输入空间可以是非常大的集合。例如，所有可能的字符串组合、所有可能的整数等。这些集合的大小通常是无限的或非常大的。

  2. 输出空间的有限性：

    • 输出空间是哈希表的大小，即数组的长度。这个长度是有限的，因为计算机的内存是有限的，哈希表的大小通常是一个固定的数值。

  3. 映射的必要性：

    • 哈希函数的作用是将大输入空间映射到小输出空间，以便在有限的内存中高效地存储和检索数据。

  4. 冲突的不可避免性：

    • 由于输入空间远大于输出空间，必然会有不同的输入映射到相同的输出值，这就是哈希冲突。

举个例子

假设你有一个哈希表，其数组长度为 1000（输出空间），而你需要存储的可能输入是所有可能的 32 位整数（输入空间）。32 位整数的可能值有 2^32 个（约 43 亿），显然远大于 1000。因此，多个不同的整数可能会映射到同一个数组索引，导致冲突。

这种映射机制是哈希表设计中的一个基本挑战，处理冲突的方法（如链地址法和开放地址法）就是为了解决这个问题。

树

递: 向下
归: 向上

堆

堆是一种特殊的树形数据结构，其中每个节点都满足特定的堆性质。堆通常用于实现优先队列（Priority Queue），因为它可以高效地支持插入和删除操作，同时保持元素的有序性。

堆有两种主要类型：

  • 最大堆（Max Heap）：在最大堆中，每个节点的值都大于或等于其子节点的值。
  • 最小堆（Min Heap）：在最小堆中，每个节点的值都小于或等于其子节点的值。

Q：数据结构的“堆”与内存管理的“堆”是同一个概念吗？

两者不是同一个概念，只是碰巧都叫“堆”。

数据结构的“堆”是基于数组实现的树形数据结构，而内存管理的“堆”是内存管理机制。

图