哈希表

一、题目形容： 题目内容 题目示例 题目解析 1 <= nums.length <= 104-107 <= nums[i] <= 1070 <= k <= 107 二、思路剖析：咱们拿到本题，读取题意要求在一组整数数组中，求出差值为k的数对对数k-diff。在思考如何解答该题之前，须要明确如下几点细节： nums数组元素都是整数索引地位i与地位j,不能相等k-diff数对关系：nums[i] - nums[j] = k -> nums[i] = nums[j] + k -〉 nums[i] - k = nums[j]k-diff数对，存在雷同数对状况，但后果只取1次 因而，咱们的对题目中进行具体理解了，因为会排除反复的数对，咱们很容易想哈希表来构建 办法一：构建哈希表 数对中反复场景如示例一中差值为k=1,(1,3) & (3,1)视为一种状况，则要定义两个哈希表来贮存哈希表能够通过字典k-value或者汇合set(),本题无需思考索引关系定义ans,numset两个汇合当 nums[i] > nums[j],则nums[j] = nums[i] - k在numset中，取最小的那一个则ans.add(nums[i]-k),当 nuns[i] < nums[j],则nums[j] = nums[i] + k 在numset中，取较小的那一个则ans.add(nums[i]) 根据上述思路，咱们应用python代码能疾速实现，代码如下：class Solution(object): def findPairs(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ ans = set() numset = set() for num in nums: if num - k in numset: ans.add(num-k) if num + k in numset: ans.add(num) numset.add(num) return len(ans)复制代码 ...

哈希表哈希表是一种常见的数据结构，在解决算法面试题的时候常常须要用到哈希表。哈希表最大的长处是高效，在哈希表中插入、删除或查找一个元素都只须要O（1）的工夫。因而，哈希表常常被用来优化工夫效率。 哈希表的设计设计哈希表的前提是待存入的元素须要一个能计算本人哈希值的函数。 哈希表最重要的特点是高效，只须要O(1)的工夫就能将元素存入或读出。 插入、删除和随机拜访都是O(1)的容器设计一个数据结构，使如下3个操作的工夫复杂度都是O（1）。字段转数组不就是O(N)? /** * Initialize your data structure here. */var RandomizedSet = function () { this.numToLocation = new Map(); this.nums = []};/** * Inserts a value to the set. Returns true if the set did not already contain the specified element. * @param {number} val * @return {boolean} */RandomizedSet.prototype.insert = function (val) { if (this.numToLocation.has(val)) { return false } this.numToLocation.set(val, this.nums.length); this.nums.push(val); return true;};/** * Removes a value from the set. Returns true if the set contained the specified element. * @param {number} val * @return {boolean} */RandomizedSet.prototype.remove = function (val) { if (!this.numToLocation.has(val)) { return false; } let location = this.numToLocation.get(val); this.numToLocation.set(this.nums[this.nums.length - 1], location); this.numToLocation.delete(val); // 数组删除对应，这里是把数据最末位的元素笼罩要删除的元素，再把数组长度减1，通过这种技巧来达到工夫复杂度为O(1) this.nums[location] = this.nums[this.nums.length - 1]; this.nums.length--; return true;};/** * Get a random element from the set. * @return {number} */RandomizedSet.prototype.getRandom = function () { // 随机生成0到this.nums.length范畴内的一个整数 let p = parseInt(Math.random() * this.nums.length); return this.nums[p];};/** * Your RandomizedSet object will be instantiated and called as such: * var obj = new RandomizedSet() * var param_1 = obj.insert(val) * var param_2 = obj.remove(val) * var param_3 = obj.getRandom() */最近起码应用缓存请设计实现一个最近起码应用（Least Recently Used，LRU）缓存，要求如下两个操作的工夫复杂度都是O（1）/** * @param {number} capacity */var LRUCache = function(capacity) { this.cache = new Map() this.capacity = capacity};/** * @param {number} key * @return {number} */LRUCache.prototype.get = function(key) { const { cache } = this if(!cache.has(key)){ return -1 } const val = cache.get(key) cache.delete(key) cache.set(key, val) return val};/** * @param {number} key * @param {number} value * @return {void} */LRUCache.prototype.put = function(key, value) { const { cache, capacity } = this if(cache.has(key)){ cache.delete(key) } if(cache.size === capacity){ const it = cache.keys() cache.delete(it.next().value) } cache.set(key,value)};/** * Your LRUCache object will be instantiated and called as such: * var obj = new LRUCache(capacity) * var param_1 = obj.get(key) * obj.put(key,value) */哈希表的利用在算法面试中哈希表是常常被应用的数据结构，如用哈希表来记录字符串中每个字符呈现的次数或每个字符呈现的地位。 ...

对于哈希表哈希表的概念散列表也叫哈希表（Hash table），是依据关键字（key）而间接拜访在内存存储地位的数据结构。 在很多高级语言中都有哈希表的身影，比方在Python中，有一种数据结构叫做dict，中文翻译是字典，应该是基于哈希表实现的。上面以生存中查电话号码作为一个艰深的例子，解说什么是哈希表。 一个例子了解哈希表能够把哈希表设想成一本依照人名首字母顺序排列电话簿，当咱们要查找张三的电话号码时，能够轻易得悉张三的首字母是Z。现实状况下，张三可能在电话簿Z结尾的第一个，不现实的状况下，可能要往后再找几个人。 显然，依据姓名首字母查找电话，要比挨个查找快很多，这就是哈希表的特点，快。 与下面例子所对应的哈希表相干名词: 哈希表：电话簿关键字(key)：姓名，如张三哈希函数(F)：计算姓名的首字母的办法，参数是姓名，返回是对应的首字母哈希地址：哈希函数的返回值，例子中，能够将A-Z了解为哈希地址什么是抵触对于不同关键词，通过哈希函数的计算，可能失去同一哈希地址。比方，只管奔走儿灞(key1)和灞波儿奔(key2)是不同的名字（key1≠key2）但通过哈希函数计算失去的是同一后果(F(key1)=F(key2)=B)，他们名字的首字母都是B。这种状况就叫做抵触。 解决抵触的办法解决抵触的办法有很多种，比方凋谢地址法和链地址法，能够依据具体应用场景来抉择。一般来说，在理论我的项目和开发中采纳链地址法比拟多。 链地址法的基本思路是，把雷同哈希地址的关键字放在同一个链表中。 采纳链地址法解决抵触的哈希表，能够了解为数组和链表的组合。在上图中，寄存首字母的是一个长度为26的数组，而数组的每一个元素能够看作是一个单链表，链表的数据域寄存着姓名，指针域指向下一个寄存雷同首字母的姓名的节点。 字典的设计下面咱们对哈希表有了一个大略的理解，接下来设计并实现一个字典(dict)，在这个字典中，能够寄存键值对，也能够依据键(key)获取对应的值(val)。 根本思维：采纳链地址法，用定长数组(Array) + 单链表的形式示意字典，假设数组长度为SIZE，初始化状态的哈希表是一个元素全为0的数组。存键值对：给定一个键值对(key1, val1)，通过哈希函数F计算失去哈希值(hash_code)，也即hash_code1 = F(key1)。而后，通过hash_code1 % SIZE失去地址(因为是在数组中的地位，这里用Array[index]示意)，取模操作是为了确保该地址在数组地址的范畴内。接着，新建一个单链表节点（节点1），指针域next为NULL，数据域寄存key1和val1。最初，在Array[index]中寄存指向节点1的指针。发生冲突：给定一个键值对(key2, val2)，key2≠key1，如果通过哈希函数计算，hash_code2 = hash_code1，那么将失去同一个地址Array[index]，此时发生冲突，因为数组此地位中曾经寄存了指向节点1的指针。解决抵触: 新建一个单链表节点（节点2），数据域保留key2和val2，指针域next为NULL。让节点1的next指针指向节点2即可解决抵触，这就是链地址法，也叫拉链法，前面的抵触，持续应用此办法解决即可。更新操作：在后面咱们插入了键值对(key1, val1), 如果在此基础上又须要插入新的键值对(key1, val0),其中val0≠val1，就须要进行更新操作。有两种办法，第一种是间接将此键值的节点作为数组对应地位的第一个节点，第二种是在对应数组地位找到key=key1的节点，而后更新其val指针。查字典：给定一个key，查val。首先要计算出地址Array[index] = F(key) % SIZE，如果有数据，此地址会寄存一个指向单链表节点的指针，接着比照该指针指向的节点的数据域key是否与要查找的key相等。现实状况下是相等的，但因为抵触的存在，可能须要沿着节点的next指针往下找，也因而，哈希算法的工夫复杂度并没有O(1)。找到数据后，返回即可。如果没数据，Array[index]=0，返回NULL。字典的示意/* 字典类型 */#define DICT_TYPE_INT 0#define DICT_TYPE_STR 1typedef struct dict_entry { /* 后继节点 */ struct dict_entry *next; /* 键 */ void *key; /* 值 */ void *val;}dict_entry;typedef struct dict { /* 哈希函数 */ unsigned int (*hash)(void *key); /* table数组用于寄存dict_entry指针 */ dict_entry **table; /* table数组的长度 */ int size; /* 掩码（size-1） */ int sizemask;}dict;首先看dict_entry构造体，它有三个成员，别离用来示意后继节点next指针和键与值，用以示意单链表的节点。 接着是dict构造体，用来示意字典自身。 ...

哈希表定义及实现哈希表也叫散列表，是快速执行查找，删除，插入的技术，不支持元素排序信息。原理是通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。关键码值到存储位置的映射被称为哈希函数也叫散列函数，当不同关键key被映射到同一value时，称为冲突。解决冲突主要有：分离链接法：对Hash表中每个Hash值建立一个冲突表，即将冲突的几个记录以表的形式存储在其中。开发定址法：根据冲突算法找到空的单元为止（线性探测法，平方探测法...）。 编程实例算法实现采用平方探测法的实现放在git@code.aliyun.com:c-program/projecteuler.git上projecteulerccommonstruct目录下elr_hash_int.h elr_hash_int.c两个单元内。 解决问题https://www.hackerrank.com/ch...要求用一个map结构存放名字name和电话phone。 定义结构#define MaxStr 20typedef unsigned long int Index;typedef Index Position;typedef char *KeyType;typedef long int *ValueType;struct HashTbl;typedef struct HashTbl *HashTable;enum KindOfEntry { Legitimate, Empty, Deleted };struct HashEntry { KeyType Key; ValueType Value; enum KindOfEntry Info;};typedef struct HashEntry Cell;struct HashTbl { long int TableSize; Cell *TheCells;};初始化及释放HashTable InitializeTable(long int TableSize) { HashTable H; long int i; H = malloc(sizeof(struct HashTbl)); if (H == NULL) { printf("Out of space!\n"); } H->TableSize = TableSize; H->TheCells = malloc(sizeof(Cell) * H->TableSize); if (H->TheCells == NULL) { printf("Out of space!\n"); } for (i = 0; i < H->TableSize; i++) { H->TheCells[i].Info = Empty; H->TheCells[i].Key = NULL; H->TheCells[i].Value = 0; } return H;}void DestroyTable(HashTable H) { int i; if (H == NULL) { return; } for (i = 0; i < H->TableSize; i++) { H->TheCells[i].Info = Empty; if (H->TheCells[i].Key != NULL) { free(H->TheCells[i].Key); } } free(H);}哈希及冲突插入操作Position Hash(KeyType Key, long int TableSize) { long int keyValue = 0; register unsigned char *p; for (p = (unsigned char *)Key; *p; p++) { keyValue = 31 * keyValue + *p; } return keyValue % TableSize;}int KeyEqual(KeyType a, KeyType b) { if ((a == NULL) || (b == NULL)) { return 1; } return strcmp(a, b) == 0 ? 0 : 1;}int Find(KeyType Key, HashTable H, Position *Pos) { Position CurrentPos; long int CollisionNum; int rst = 0; CollisionNum = 0; CurrentPos = Hash(Key, H->TableSize); while (1) { if (H->TheCells[CurrentPos].Info == Empty) break; if (KeyEqual(H->TheCells[CurrentPos].Key, Key) == 0) { rst = 1; break; } CurrentPos += (++CollisionNum << 1) - 1; if (CurrentPos >= H->TableSize) { CurrentPos -= H->TableSize; } } *Pos = CurrentPos; return rst;}void Insert(KeyType Key, ValueType Value, HashTable H) { Position Pos; int exist; exist = Find(Key, H, &Pos); H->TheCells[Pos].Info = Legitimate; if (!exist) { H->TheCells[Pos].Key = malloc(sizeof(char) * MaxStr); } strcpy(H->TheCells[Pos].Key, Key); H->TheCells[Pos].Value = Value;}调用解决问题#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>int main() { long int n = 0; scanf("%ld", &n); HashTable H = InitializeTable(n * 2); for (int i = 0; i < n; i++) { char name[20]; long int phone; scanf("%s %ld", name, &phone); Insert(name, phone, H); } for (int i = 0; i < n; i++) { char name[20]; Position Pos; int exist; scanf("%s", name); // while (() != '\n'); exist = Find(name, H, &Pos); if (exist == 1) { ValueType Value = H->TheCells[Pos].Value; printf("%s=%ld\n", name, Value); } else { printf("Not found\n"); } if (getchar() == EOF) break; } DestroyTable(H); return 0;}

线性查找的时间复杂度O(n)，二分查找为O(logn)，有没有时间复杂度为O(1)的查找吗？ 当然有，这就是散列表。散列函数散列函数“将输入映射到数字”。其必须满足一些要求。它必须是一致的。对于同样的输入，输出必须是一样的。最理想的情况是,将不同的输入映射到不同的数字。这样，不同的输入就会映射到不同的位置。这样就可以使用散列函数将输入映射到数组的不同位置，从而得到一个简单的散列表（hash table）。散列表是目前该书介绍的第一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存,但散列表更复杂,它使用散列函数来确定元素的存储位置。散列表由键和值组成，将键映射到值。同时散列表也被称为散列映射、映射、字典和关联数组。比如，Python提供的散列表实现为字典。Python内置字典的用法：>>> book = dict() # 创建空字典>>> book[“apple”] = 0.67 # 添加键值对>>> book[“milk”] = 1.49 # 添加键值对>>> book[“avocado”] = 1.49 # 添加键值对>>> print(book) # 打印当前散列表{‘apple’: 0.67, ‘milk’: 1.49, ‘avocado’: 1.49}>>> print(book[“avocado”]) # 散列表使用键查找值1.49应用案例将散列表用于查找通过键快速查找其关联的值。比如，电话簿姓名为键，电话号码为值DNS解析(DNS resolution)域名为键，IP地址为值防止重复比如，投票限制每人只能投一票。可以将某人的信息（如，姓名、IP等）作为键存到散列表内，每次用户投票前，先看看之前有没有投过，没投的话允许投票，并将信息存到散列表内，如果投过票，则不允许再投。将散列表用作缓存缓存是一种常用的加速方式,所有大型网站都使用缓存,而缓存的数据则存储在散列表中。缓存的工作原理:网站将数据记住,而不再重新计算，这样的好处是减少响应的时间，同时也节省了服务器的计算资源。当访问网站的页面时,它首先检查散列表中是否存储了该页面。仅当URL不在缓存中时,你才让服务器做些处理,并将处理生成的数据存储到缓存中,再返回它。这样,当下次有人请求该URL时,你就可以直接发送缓存中的数据,而不用再让服务器进行处理了。冲突(collision)最理想的情况是,散列函数将不同的输入映射到不同的数字，但几乎不可能编写出这样的散列函数。冲突：给两个键分配的位置相同。处理冲突的方式很多,最简单的办法如下:如果两个键映射到了同一个位置,就在这个位置存储一个链表。这种处理方式也有可能出现最糟的情况，如，除第一个位置外,整个散列表都是空的,而第一个位置包含一个很长的列表，这时查找速度等同于链表的查找速度，会很慢。好的散列函数很少导致冲突，这样会将键均匀地映射包散列表的不同位置，从而使链表不会太长。性能在平均情况下,散列表执行各种操作的时间都为O(1)。O(1)被称为常量时间。常量时间并不意味着马上,而是说不管散列表多大,所需的时间都相同。在最糟情况下,散列表所有操作的运行时间都为O(n)——线性时间。要避免冲突，需要有：较低的填装因子；填装因子 = 散列表包含的元素数 / 位置总数填装因子度量的是散列表中有多少位置是空的。 一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度（resizing） 。调整长度需要重新创建新的存储空间，然后使用散列函数将所有的元素都插入到新的散列表内，所以开销较大。但平均而言,即便考虑到调整长度所需的时间,散列表操作所需的时间也为O(1)。填装因子越低,发生冲突的可能性越小,散列表的性能越高。一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。良好的散列函数。良好的散列函数让数组中的值呈均匀分布。糟糕的散列函数让值扎堆,导致大量的冲突。 请继续关注我的公众号文章