哈希表

一、题目形容： 题目内容 题目示例 题目解析 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构造体，用来示意字典自身。 ...