在一个天朗气清的日子，小灰登上了线上的redis打算查询数据。然而他只记得前缀而不知道整个键是多少，于是在命令行敲入了“keys xxx*”命令。瞬间服务卡死，报警邮件堆满了邮箱，而小灰，只能目瞪狗呆的等待着即将降临的case study。基本上，keys

这个特定的算法就叫hash算法，hash算法并不是一个固定不变的算法。只要是能达到这个目的的算法都可以说hash算法。例如MD5,SHA，String.hashcode()都是hash算法。另外不同的输入可能会得出相同的hash值，那么这种现象称为hash

哈希表又叫散列表，这里用数组和链表实现。//编写一个hash方法。//先计算该no对应的链表。//编写Emplinkedlist，存放的是雇员信息。//将curEmp定位到链表的最后。//使用辅助指针遍历

通过上一节的学习，我们知道，散列表的查询效率并不能简单说成是O。它跟散列函数、装载因子、散列冲突等地都有关系。今天我们来学一下，如何设计一个可以应对各种异常情况的工业级散列表，来避免在散列冲突的情况下，散列表性能的急剧下降，并且能抵抗散列碰撞攻击？过于复杂

在 memcached 节点失效的情况下，集群没有必要做任何容错处理。果发生了节点失效，应对的措施完全取决于用户。节点失效时，下面列出几种方。在失效节点被恢复或替换之前，还有很多其他节点可以应对节。点失效带来的影响。，客户端添加或移除节点，会导致所有的缓存

　　redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表，而每个哈希表节点就保存了字典中的一个键值对。dictEntry **table; //存放一个数组的地址，数组存放着哈希表节点dictEntry的地址。unsigned

　　在一个长度为n的数组里的所有数字都在0到n-1的范围内。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应第一个重复的数字是2。　　第一种思路：寻找重复的数字最容易想到的就是先排序后查找，因为如果数字出现重复，那么排序后相邻的数字必定

127.0.0.1:6379> hmset hash_key key3 v3 key4 v4 key5 v5

实现了一个非递归的 golang map。哈希表在某些场景下可以称为字典，用途是可以根据 键key 索引该键对应的 值value。哈希表是什么，可以参考：数据结构和算法。目前实现的哈希表 Map，不是用链表数组数据结构实现的，而是以平衡二叉查找树形式来实现

散列表，是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f，对任意给定的关键字值key，代入函数后若能得到包含该关键字的

HashMap 作为我们日常使用最频繁的容器之一，相信你一定不陌生了。今天我们就从HashMap 的底层实现讲起，深度了解下它的设计与优化。我在 05 讲分享 List 集合类的时候，讲过 ArrayList 是基于数组的数据结构实现的，LinkedLis

为什么需要哈希表？在上学时需要学习英语，而在当时有很多的电子词典，同学们遇到不会的单词，只要在这个电子词典上输入单词的英文，就可以查出中文的含义。但是，同学们还是倾向于使用电子词典。在我们程序员的世界里，往往也需要在内存中存放这样一个“词典”，方便我们进行

typedef struct dict{　　//类型特定函数　　dictType *type;　　//私有数据　　void *privateata;　　//哈希表　　dictht ht[2];　　//rehash 索引，rehash未进行时，值为-1　　i

哈希表可以通过关键字直接找到数据的存储位置，不需要进行任何的比较，也就是说，哈希表建立了关键字和存储地址之间的一种直接映射关系。其查找的效率相较于前面所学习的查找算法是更高的。在设计哈希函数时，要尽量地避免冲突现象的发生。对于哈希表而言，冲突只能尽可能地少

unsigned long iterators; /* number of iterators currently running */. dictEntry **table; //哈希表数组 这是个数组 数组元素为 dictEntry指针 dictEnt

那个深夜，我登上了公司的服务器，在Redis 命令行里敲入 keys* 后，线上开始报警，服务瞬间被卡死，我只能举起双手，焦急地等待几千万key被慢慢扫描，束手无策万念俱灰的时候，我收到了leader的短信：你明天不用来上班了。作为一种可以称为数据库的组件

散列表，是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。有一个公司,当有新的员工来报道时,要求将该员工的信息加入,当输入该员工的 id 时

buf：char类型的数组，存储具体字符，最后一个字节保存了空字符‘\0‘。SDS字符串中len保存了字符串的长度，所以获取SDS的时间复杂度是O。SDS在修改前，先会判断字符串空间是否满足修改所需要的要求，如果不满足的话，会先将空间拓展至执行修改所需要的

edis源码的dict.c主要实现了基于hash表的操作，如增删改查，对哈希表大小的扩容和缩容，以及对哈希表的rehash和增量rehash等。在源码的dictScan函数中，非常巧妙精美地实现了对哈希表的迭代查找，非常建议去看一下。

在Redis中，dict是一个基于哈希表的算法，采用拉链法解决冲突，并在装载因子超过预定值时自动扩展，引发重哈希。之所以这样设计是为了避免重哈希期间单个请求的响应时间剧烈增加。type：对象的数据类型，可能的取值OBJ_STRING、OBJ_LIST、OB