概述：简单地说，哈希表是一种数据结构，它依靠哈希函数来组织数据，以达到常量级别的时间复杂度，对于插入和查找非常高效。哈希表的两种：哈希集是集合数据结构的一种实现，用于存储唯一值。Hashmap是map数据结构的一种实现，用于存储（key,value）键值对。大多数高级编程语言标准库都有内置的哈希表模板。1、哈希表的原理哈希表的核心思想是使用哈希函数将键映射到桶中。更准确地说，当我们插入一个新的key时，hash函数会决定这个key应该被分配到哪个bucket中，并将key存储到对应的bucket中；当我们要查找某个键时，哈希函数表会使用相同的哈希函数查找对应的桶，并且只在那个特定的桶内进行搜索。示例在示例中，我们使用y=x%5作为散列函数。我们用这个例子来完成插入和查找策略：插入：我们通过哈希函数解析键，将它们映射到对应的桶中。比如1987分配给2号桶，24号分配给4号桶。搜索：我们通过相同的hash函数解析key，只在特定的bucket中搜索。如果我们搜索1987，我们将使用相同的哈希函数将1987映射到2。因此我们在桶2中搜索，我们成功地在该桶中找到了1987。比如我们查找23，将23映射到3，在3号桶中查找，发现23不在3号桶中，也就是说23不在哈希表中。Hash哈希函数：可以看出，元素的存储位置与其关键字F有对应关系，key可以通过hash进行映射function搜索时输出元素的索引位置（桶），对应关系F就是哈希函数。哈希函数是哈希表中最重要的组成部分，用于将键映射到特定的桶。在上面的示例中，y=x%5用作哈希函数，其中x是键值，y`是分配的桶的索引。哈希函数会依赖键值的范围和桶的个数。以下是散列函数的一些示例：散列函数的设计是一个悬而未决的问题。这个想法是将键尽可能多地分布到桶中，理想情况下，一个完美的哈希函数应该是键和桶之间的一对一映射。然而，在大多数情况下哈希函数并不完美，它需要在桶的数量和桶的容量之间进行权衡。2.冲突解决理想情况下，如果我们的散列函数是完美的一对一映射，我们就不需要处理冲突。不幸的是，在大多数情况下，冲突几乎是不可避免的。比如我们之前的hash函数(y=x%5)中，1987和2都被赋值到了bucket2，这就是碰撞(所以映射位置叫做bucket，因为碰撞也需要在bucket中进行)bucket二次搜索找到元素的位置）。您可以简单地使用数组将键存储在同一个桶中。如果N是可变的或很大，我们可能需要改用高度平衡的二叉树。3.复杂度分析如果一共有M个键，那么在使用哈希表时，可以达到O(M)的空间复杂度。哈希表的时间复杂度与设计有很强的关系。以使用数组将值存储在同一个桶中为例。理想情况下，桶大小足够小，可以看作是一个常数。插入和搜索的时间复杂度都是O(1)。但在最坏的情况下，最大桶大小将是N。插入的时间复杂度为O(1)，搜索的时间复杂度为O(N)。内置哈希表的原理高级编程语言内置哈希表的典型设计是：键值可以是任何可以被哈希的类型。可哈希类型的值将具有哈希码。该哈希码将在映射函数中用于获取桶索引。每个桶包含一个数组，该数组最初将所有值存储在同一个桶中。如果同一个桶中的值过多，则将这些值保存在一棵高度平衡的二叉搜索树中。插入和查找的平均时间复杂度仍然是O(1)。使用高度平衡的BST，最坏情况下的插入和搜索时间复杂度为O(logN)。这是插入和搜索之间的权衡。欢迎关注微信公众号：爱写bug
