| 数据结构 | 您所在的位置：网站首页 › 集合倒序输出什么意思 › 数据结构 |
数据结构
|
哈希表（本篇主要讲哈希集合）
部分内容来源于博主@SnailMann 前提在实际编程中，我们常常面临着两个问题：存储和查询，这两个过程的效率往往制约着整个程序的效率，而我们常见的存储数据的数据结构比如线性表，树，图等，数据在结构中的位置往往是不明确的，当我们在这些数据结构中要查询一个数据，都避免不了去执行查询算法，去遍历数据结构，拿关键字和结构中的数据进行一一比较，从而得到想要的数据，我们就希望能不能不通过比较就能获得我们想要的结果呢？ 答案是有的，不通过任何比较，一次存储便能取得所查记录，但这就必须在记录的存储位置和他的关键字之间建立一个确定的对应关系f，使得每个关键字和结构中的唯一的存储位置相对应，这个关系就是我们所说的哈希函数f(x),在这个思想上建立起来的表就成为哈希表。 介绍哈希表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。 有两种不同类型的哈希表：哈希集合和哈希映射。 哈希集合是集合数据结构的实现之一，用于存储非重复值。 哈希映射是映射 数据结构的实现之一，用于存储(key, value)键值对。 在标准模板库的帮助下，哈希表是易于使用的。大多数常见语言（如Java，C ++ 和 Python）都支持哈希集合和哈希映射。 通过选择合适的哈希函数，哈希表可以在插入和搜索方面实现出色的性能。 原理哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说， 当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中； 当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索。 插入：我们通过哈希函数解析键，将它们映射到相应的桶中。 例如，1987 分配给桶 2，而 24 分配给桶 4。搜索：我们通过相同的哈希函数解析键，并仅在特定存储桶中搜索。 如果我们搜索 1987，我们将使用相同的哈希函数将1987 映射到 2。因此我们在桶 2 中搜索，我们在那个桶中成功找到了 1987。 例如，如果我们搜索 23，将映射 23 到 3，并在桶 3 中搜索。我们发现 23 不在桶 3 中，这意味着 23 不在哈希表中。 设计哈希集合不使用任何内建的哈希表库设计一个哈希集合 具体地说，你的设计应该包含以下的功能 add(value)：向哈希集合中插入一个值。 contains(value) ：返回哈希集合中是否存在这个值。 remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。 示例: MyHashSet hashSet = new MyHashSet(); hashSet.add(1); hashSet.add(2); hashSet.contains(1); // 返回 true hashSet.contains(3); // 返回 false (未找到) hashSet.add(2); hashSet.contains(2); // 返回 true hashSet.remove(2); hashSet.contains(2); // 返回 false (已经被删除) 注意： 所有的值都在 [1, 1000000]的范围内。 操作的总数目在[1, 10000]范围内。 不要使用内建的哈希集合库。 class MyHashSet { public: /** Initialize your data structure here. */ vector hash; MyHashSet() { hash = vector(1000001, false); } void add(int key) { hash[key] = true; } void remove(int key) { if(hash[key]) { hash[key] = false; } return; } /** Returns true if this set contains the specified element */ bool contains(int key) { if(hash[key]) { return true; } return false; } }; /** * Your MyHashSet object will be instantiated and called as such: * MyHashSet* obj = new MyHashSet(); * obj->add(key); * obj->remove(key); * bool param_3 = obj->contains(key); */ 设计哈希映射不使用任何内建的哈希表库设计一个哈希映射 具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。 get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。 remove(key)：如果映射中存在这个键，删除这个数值对。 示例： MyHashMap hashMap = new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // 返回 1 hashMap.get(3); // 返回 -1 (未找到) hashMap.put(2, 1); // 更新已有的值 hashMap.get(2); // 返回 1 hashMap.remove(2); // 删除键为2的数据 hashMap.get(2); // 返回 -1 (未找到) 注意： 所有的值都在 [1, 1000000]的范围内。 操作的总数目在[1, 10000]范围内。 不要使用内建的哈希库。 class MyHashMap { public: /** Initialize your data structure here. */ vector hash; MyHashMap() { hash = vector(1000001,-1); } /** value will always be non-negative. */ void put(int key, int value) { hash[key] = value; } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ int get(int key) { if(hash[key] == -1) { return -1; }else{ return hash[key]; } } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ void remove(int key) { if(hash[key] == -1) { return; }else { hash[key] = -1; } } }; /** * Your MyHashMap object will be instantiated and called as such: * MyHashMap* obj = new MyHashMap(); * obj->put(key,value); * int param_2 = obj->get(key); * obj->remove(key); */这两道题主要用于理解哈希集合和哈希映射的概念 哈希集合在c++ stl中的应用 #include // 当时用set时引用的模板库 int main() { // 创建一个哈希集合 unordered_set hashset; // 插入新的关键字 hashset.insert(3); hashset.insert(2); hashset.insert(1); // 删除关键字 hashset.erase(2); // 判断关键字是否在哈希集合中，如果在方法返回负数 if (hashset.count(2) |
在示例中，我们使用 y = x ％ 5 作为哈希函数。让我们使用这个例子来完成插入和搜索策略：【本文地址】