![[Redis数据结构|Java实现] 二：字典（Map）](http://www.mshxw.com/aiimages/31/778774.png "[Redis数据结构|Java实现] 二：字典（Map）")
[Redis数据结构|Java实现] 二：字典（Map）
概念：Redis中的字典，底层是使用hashtable实现，一个哈希表里面可以有多个 哈希表节点，每个哈希表节点都保存着一个键值对。 实现思路：
哈希表实现：数组+链表
哈希表的实现主要要考虑以下两个方面？解决方案： 哈希表节点定义Map的常规操作实现
put实现get实现（不要去遍历所有节点） 扩容实现
Redis里面扩容实现 完整代码：测试代码：测试结果：
[Redis数据结构|Java实现] 二：字典（Map）概念：Redis中的字典，底层是使用hashtable实现，一个哈希表里面可以有多个 哈希表节点，每个哈希表节点都保存着一个键值对。实现思路：
主要考虑以下几个问题：
哈希表怎么实现？
哈希表节点怎么定义？
Map的常规操作怎么实现？
put实现get实现replace实现
怎么实现扩容？
哈希表实现：数组+链表哈希表底层直接用数组+链表的经典实现方式即可。
为什么这样实现呢？
哈希表的实现主要要考虑以下两个方面？- 计算好哈希值之后，就可以知道需要存储到对应桶的位置，那么如何快速定位到需要存储到的桶的位置。对于哈希值同样的数据，怎么存储？（怎么解决哈希冲突）
针对第一个问题：
使用数组来存储桶，则计算好索引的位置之后，直接获取数组指定的位置即可，时间复杂度为O(1)。
第二个问题：
哈希值同样的数据，直接用链表存储即可。
哈希表节点定义首先哈希表节点需要存储键值对，所以肯定需要保存key,value。
其次还需要保存它的下一个节点，所以肯定需要一个 next指针。（c里面叫指针）
所以可以定义成以下结构：
private static class Node{
String key;
Node next;
String val;
public Node(String key,String val){
this.key = key;
this.next = null;
this.val = val;
}
}
Map的常规操作实现
put实现
put的实现思路：put(key,val)，首先计算key的hashcode，然后利用hashcode对数组的长度取模，得到桶的下标，然后去遍历这个桶里面的元素，如果没有同样的（equal判断)，就加到这个桶保存的链表的尾部即可。
public boolean put(String key,String val){
int index = key.hashCode()%buf.length;
Node node = new Node(key,val);
if(buf[index] == null){
buf[index] = node;
used++;
}else {//使用链表存储
if(isContain(buf[index],key))
return false;
addOnLast(buf[index], node);
}
keyNumber++;
return true;
}
get实现（不要去遍历所有节点）
get的实现思路：get(key)，首先计算key的hashcode，然后利用hashcode对数组的长度取模，得到桶的下标，然后去遍历这个桶里面的元素，如果没有同样的（equal判断)，直接返回null，否则返回对应节点的val即可。
public String get(String key){
int index = key.hashCode()%buf.length;
if(buf[index] == null)
return null;
Node root = buf[index];
while (root != null){
if(root.key.equals(key))
return root.val;
root = root.next;
}
return null;
}
扩容实现
首先，为什么需要扩容？
因为单哈希冲突比较多时，一个桶中存储的链表可能会很长，这时候即使定位到了桶的位置，也需要遍历这个很长的链表，这会造成比较大的开销。
Redis里面扩容实现Redis里面字典的扩容实现是比较独特的，它通过使用两个hashtable(buf,buf2)，然后进行扩容。
具体操作：先计算负载因子，当负载因子满足一定值时，则执行扩容操作。
具体扩容：给buf2分配内存，将buf2当成buf，然后将原先buf中的数据重新添加即可，最后把buf设置为buf2，方便下一次扩容。
private int getLoadFactor(){
return used/buf.length;
}
public void rehash(){
if(getLoadFactor() == 0){
return;
}
buf2 = new Node[buf.length*2];//将其容量加倍
Node[] temp = buf;
buf = buf2;
this.used = 0;
this.keyNumber = 0;
buf2 = null;
for(int i=0;i< temp.length;i++){
Node root = temp[i];
if(root != null){//统计
while (root != null){
put(root.key,root.val);
root = root.next;
}
}
}
}
完整代码：
package redis.Map;
public class RedisMap {
private static final int DEFAULT_SIZE = 5;
private int used;
private int keyNumber;
//buf2用来做扩容操作
private Node[] buf,buf2;
public RedisMap(){
buf = new Node[DEFAULT_SIZE];
}
public RedisMap(int capacity){
buf = new Node[capacity];
}
private static class Node{
String key;
Node next;
String val;
public Node(String key,String val){
this.key = key;
this.next = null;
this.val = val;
}
}
private int getLoadFactor(){
return used/buf.length;
}
public void rehash(){
if(getLoadFactor() == 0){
return;
}
buf2 = new Node[buf.length*2];//将其容量加倍
Node[] temp = buf;
buf = buf2;
this.used = 0;
this.keyNumber = 0;
buf2 = null;
for(int i=0;i< temp.length;i++){
Node root = temp[i];
if(root != null){//统计
while (root != null){
put(root.key,root.val);
root = root.next;
}
}
}
}
public boolean put(String key,String val){
int index = key.hashCode()%buf.length;
Node node = new Node(key,val);
if(buf[index] == null){
buf[index] = node;
used++;
}else {//使用链表存储
if(isContain(buf[index],key))
return false;
addOnLast(buf[index], node);
}
keyNumber++;
return true;
}
public boolean replace(String key,String newVal){
if( contains(key)){//包含才替换
Node node = new Node(key,newVal);
for(int i=0;i");
node = node.next;
}
System.out.println();
}
//判断键是否相同
private boolean isContain( Node node, String key){
while (node != null){
if(node.key.equals(key))
return true;
else
node = node.next;
}
return false;
}
//将node添加到root的尾部节点
private void addOnLast( Node root, Node node){
while (root.next != null){
root = root.next;
}
root.next = node;
}
public boolean contains(String key){
for(int i=0;i
测试代码：
package redis.Map;
public class RedisMapTest {
public static void main(String[] args) {
RedisMap redisMap = new RedisMap();
//put操作
redisMap.put("a","123");
redisMap.put("b","456");
//打印信息
redisMap.printAll();
//获取
System.out.println(redisMap.get("a"));
//替换
redisMap.replace("a","777");
System.out.println(redisMap.get("a"));
//打印
redisMap.printAll();
//移除
redisMap.remove("a");
redisMap.printAll();
System.out.println(redisMap);
redisMap.put("c","123");
redisMap.put("d","456");
redisMap.put("e","123");
redisMap.put("f","456");
redisMap.put("g","123");
redisMap.put("h","456");
redisMap.put("i","123");
redisMap.put("j","456");
redisMap.printAll();
System.out.println(redisMap);
System.out.println("==========扩容为===========");
//执行扩容操作
redisMap.rehash();
redisMap.printAll();
System.out.println(redisMap);
//
redisMap.put("k","456");
redisMap.put("m","123");
redisMap.put("n","456");
//再扩容一次
System.out.println("==========最终扩容为===========");
//执行扩容操作
redisMap.rehash();
redisMap.printAll();
System.out.println(redisMap);
}
}
测试结果：
========begin print==========
index 0 :
index 1 :
index 2 :
a:123->
index 3 :
b:456->
index 4 :
123
777
========begin print==========
index 0 :
index 1 :
index 2 :
a:777->
index 3 :
b:456->
index 4 :
========begin print==========
index 0 :
index 1 :
index 2 :
index 3 :
b:456->
index 4 :
========redis map info==========
RedisMap{used=1, keyNumber=1,buf.size=5}
========begin print==========
index 0 :
d:456->i:123->
index 1 :
e:123->j:456->
index 2 :
f:456->
index 3 :
b:456->g:123->
index 4 :
c:123->h:456->
========redis map info==========
RedisMap{used=5, keyNumber=9,buf.size=5}
==========扩容为===========
========begin print==========
index 0 :
d:456->
index 1 :
e:123->
index 2 :
f:456->
index 3 :
g:123->
index 4 :
h:456->
index 5 :
i:123->
index 6 :
j:456->
index 7 :
index 8 :
b:456->
index 9 :
c:123->
========redis map info==========
RedisMap{used=9, keyNumber=9,buf.size=10}
==========最终扩容为===========
========begin print==========
index 0 :
d:456->
index 1 :
e:123->
index 2 :
f:456->
index 3 :
g:123->
index 4 :
h:456->
index 5 :
i:123->
index 6 :
j:456->
index 7 :
k:456->
index 8 :
index 9 :
m:123->
index 10 :
n:456->
index 11 :
index 12 :
index 13 :
index 14 :
index 15 :
index 16 :
index 17 :
index 18 :
b:456->
index 19 :
c:123->
========redis map info==========
RedisMap{used=12, keyNumber=12,buf.size=20}
Process finished with exit code 0
