为什么Redis性能很高，遥遥领先于MySQL？
个人分析有如下原因：
- IO多路复用
- 物理结构上来说，它是内存数据库，内存的访问速度比硬盘快几个量级。
机械硬盘的随机访问速度一般为毫秒级，SSD硬盘的随机访问速度一般为微秒级，而内存的随机访问速度一般为纳秒级。
- 逻辑结构上来说，归功于它的存储结构——哈希表，查找的时间复杂度为O(1)。
- 还有一些系统设计方面的不同
- 例如结构简单，通过单线程执行命令，避免了控制并发所需要的锁开销，例如，不用像MySQL一样，需要使用锁来控制写-写并发，使用MVCC来控制读-写并发。
- 例如持久化，不保证数据一致性，默认通过RDB的方式保存快照数据，不像MySQL，每次更改都需要日志落盘，以保证一致性。
全局哈希表
我们知道Redis是NoSQL数据库，存储的全是键值对信息。如何管理这些键值对信息，从而进行快速的查找和增删呢？这就涉及到数据结构，应该使用二叉搜索树、B树、B+树、跳表还是哈希表？
Redis的选择是哈希表，为什么呢？
- 哈希查找时拥有最快的速度，时间复杂度为O(1)，时间复杂度不会随着数据量的增加而增加，而树的时间复杂度普遍为O(logN)，时间复杂度随着数据量的增加而增加。
- 哈希表的增删时也最为简单，只需要进行单节点的修改，而树形结构，还需要额外的动作来维护树的平衡。
Redis中的哈希表类似于java中的hashmap，哈希桶中每一个元素都是一个entry对象，而一个entry对象又包含key和value两个字段。
其中Key一般是一个String类型的字符串，而value则拥有多种数据类型，如String、List、Hash、Set、Sorted Set、Stream、JSON、GEO、BitMap、HyperLog等等。
哈希冲突
随着哈希表中的元素越来越多，哈希冲突的概率也就越高，哈希冲突即多个entry在哈希桶中占用同一个位置。在产生哈希冲突时，多个entry对象会组成为一个单向链表，在查找时，先通过哈希查找确定位置，如果该位置有多个entry对象，则遍历该单向链表。
哈希冲突较多时，会影响哈希查找的速度
多个entry对象怎么组成一个单向链表？
entry对象源码如下，其中包含指向下一个entry对象的next指针，通过该指针可将多个entry串联起来。
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
新节点是怎么插入链表中的？
插入新节点时，采用的方式是头插入，原因是
- 因为新插入的entry，可能会更加频繁的使用，所以将其插入在链表头，可以加快检索速度。
- 头插入的时间复杂度为O(1)，尾插入时还需要遍历链表，时间复杂度为O(N)。
那为什么JDK1.7中hashmap使用的头插入，而JDK1.8中使用的却是尾插入？
先说说基本实现上的区别：
- 1.7版本hashmap的底层实现为数组+链表
- 1.8版本hashmap的底层实现为数组+链表+红黑树，默认在链表长度为8时，将链表转换为红黑树，转换后访问的时间复杂度由O(N)变为O(logN)，可以加快检索速度。
但为什么要改变冲突链表的插入方式？毕竟头插入的效率更高。
搜了一圈，普通说是因为头插入在并发时可能导致链表成环问题，但这十分不靠谱好吗？hashmap本来就不是线程安全的，谁会在多线程环境下用hashmap？
还有说法是代码是从新增的concurrentHashmap中拷贝过来的，因为concurrentHashmap中需要考虑多线程并发问题，使用的是尾插入方式。
哈希表扩容
在哈希冲突比较频繁时，为了使查找速度不受影响，我们不得不考虑哈希表扩容的问题了。
使用过java中hashmap应该都知道，哈希表有一个初始容量，当存储的对象数量接近设置的容量时，就会对哈希表进行扩容。所以为了避免扩容，一般会根据实际数据量设定合适的初始容量。
为什么要避免扩容？
因为哈希表的基础组成是数组和链表，而数组是无法动态调整长度的。在进行扩容时，需要创建新的数组，并为其申请分配内存空间，然后对已有数据进行rehash，再将其放到新的数组空间中。这是一个耗时操作，会影响用户请求。
redis中的情况
redis中的无法配置全局哈希表的容量，在存储了足够多的数据后，进行哈希扩容，岂不是会阻塞用户请求？
是的，如果一次性完成哈希扩容的话，是会影响用户请求的，并且数据量越多影响越大。所以redis中，进行哈希扩容的方式不是一次性扩容，而是使用一种渐进式哈希的方法。
- redis中全局哈希表的初始长度为4
/* This is the initial size of every hash table */
#define DICT_HT_INITIAL_SIZE 4
渐进式哈希
那么渐进式哈希是怎么做的？在这之前，我们先看一下redis中相关的源码定义，
- dictht：哈希表，用于管理键值对对象dictEntry
- dict ：字典，用于管理哈希表的初始化、扩容等
可以看到一个dict中存在两个哈希表，平时使用第一个，第二个处于备用状态。
在需要进行哈希扩容时，启用备用的哈希表。每当接受到客户端的请求后，先处理请求，然后顺便在旧哈希表中，从第一个位置开始每次移动一个位置上的entry对象到备用哈希表中。之后重复这个过程，直到完成所有数据的移动。
渐进式哈希巧妙将rehash的影响分摊在了每一次用户请求上，并且不会对其产生明显影响。
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;