本章完全按照《redis设计与实现》该书进行学习和总结（http://redisbook.com/）

redis中的数据结构包括
简单动态字符串
链表
字典
跳表
整数集合
压缩列表
对象
简单动态字符串
结构：

public class SDSstruct {
    //长度---传统数组要想取得长度需要遍历（节省开销）
    int len;
    //记录空闲空间
    //因为有了记录所以在存储上不需要因为修改而重新分配内存
    //达到预分配内存或者惰性分配内存（节省开销）
    int free;
    //存储空间
    char buf[];
    //C语言中的数组最后一位是空字符串（\n）来判断字符数组结束。
    //因为这个特性，C字符串只能保存文本数据，不能保存图片，视频，压缩等数据
    //而SDS是通过len判断长度而不像C是由\n判断长度结束的
}

预分配策略
当len<1MB；len=free(32len+32free+1空字符串=65)
当len>1MB；free只有1MB（32Mlen+1Mfree+1b空字符串=33MB）

链表
结构：

//链表节点
public class LinkListNodeStruts {
   LinkListNodeStruts pre;
   LinkListNodeStruts next;
   String value;
}
//链表
public class ListStruts {
   LinkListNodeStruts  head;
   LinkListNodeStruts  tail;
   long len;
   public void dup(){};
   public void free(){};
   public void match(){};
}

链表被广泛用于实现redis功能。
字典（map）
map的底层是由hash表实现的
哈希表（散列表）
原理：
哈希表hash table(key，value) 的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。
因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”。
特点：
直接定址
解决冲突
解决冲突之拉链法
上面的方法使用数组实现的，其实很多时候需要使用数组链表来做。开一个数组，数组每个元素都是一个链表。（hash函数选择，针对字符串，整数，排列，具体相应的hash方法。 碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。（https://blog.csdn.net/zeb_perfect/article/details/52574915）
哈希表会自动收缩和扩展

跳跃表
有序集合的底层实现，每一个节点（node）都保存了一条数据。
Redis中有两个地方用到了跳表
1.有序集合
2.集群节点用在节点内部数据结构
跳跃表-原理及Java实现
https://www.cnblogs.com/acfox/p/3688607.html
Node节点
key value
四个指针top down left right

package com;


import java.util.*;
public class SkipList {
    public Node head;   //头节点
    public Node tail;   //尾结点
    public int h;   //层数
    public int size;    //元素个数
    public Random rand; //每次的随机数用来确定需不需要增加层数
    public SkipList(){
        Node p1 = new Node(Node.tou,0);
        Node p2 = new Node(Node.wei, 0);
        head=p1;
        tail=p2;
        head.setRight(tail);
        tail.setLeft(head);
        h=0;
        size=0;
        rand = new Random();
    }
    public boolean isEmpty(){
        if(size==0){
            return true;
        }
        return false;
    }
    //找到需要插入位置的前一个节点
    public Node findF(String k){
        Node temp;
        temp=head;
        while(true){
            while(temp.getRight().key!=Node.wei&&temp.getRight().key.compareTo(k)<=0){
                /*
                 * 当链表最底层不为空的时候，从当前层向尾部方向开始查找，直到查找temp.getRight的下一个值大于 当前k的值为止，此时temp小于或等于当前k的值
                 *  要插入的位置即为temp之后的位置了
                 */
                temp=temp.getRight();
            }
            if(temp.getDown()!=null){
                temp=temp.getDown();
            }else{
                break;
            }

        }
        return temp;    //找到节点并返回

    }
    public int add(String k, int v){
        Node temp, temp1;
        temp=findF(k);
        int i;  //当前层数
        if(k.equals(temp.getKey())){
            System.out.println("对象属性完全相同无法添加！");
            int a=temp.value;
            temp.value=v;
            return  a;
        }
        temp1=new Node(k,v);
        temp1.setLeft(temp);
        temp1.setRight(temp.getRight());
        temp.getRight().setLeft(temp1);
        temp.setRight(temp1);
        i=0;

        while(rand.nextDouble()<0.5){   //进行随机，是否需要 在上层添加
            if(i>=h){   //若当前层数超出了高度，则需要另建一层
                Node p1 ,p2 ;
                h=h+1;
                p1=new Node(Node.tou,0);
                p2=new Node(Node.wei,0);

                p1.setRight(p2);
                p1.setDown(head);

                p2.setLeft(p1);
                p2.setDown(tail);

                head.setUp(p1);
                tail.setUp(p2);

                head=p1;
                tail=p2;
            }
            while(temp.getUp() == null){
                temp=temp.getLeft();
            }
            temp=temp.getUp();
            Node node=new Node(k,v);
            node.setLeft(temp);
            node.setRight(temp.getRight());
            node.setDown(temp1);

            temp.getRight().setLeft(node);
            temp.setRight(node);
            temp1.setUp(node);

            temp1=node;
            i=i+1;

        }

        size=size+1;
        return  0;
    }
    //节点查找
    public Node find(String k){
        Node temp=head;
        Node node;
        node=temp;
        System.out.println("查找路线"); //用于测试
        while(temp!=null){
            while(node.getRight().key!=Node.wei&&node.getRight().getKey().compareTo(k)<=0){//&&node.getRight().getValue()!=v
                node=node.getRight();
                System.out.print("--->"+node.getKey());
            }

            if(node.getDown()!=null){
                node=node.getDown();
                System.out.print("--->"+node.getKey());
            }else{
                if(node.key.equals(k)){//&&node.getRight().value==v
                    //node.setValue(111111111); //修改
                    System.out.println("--->"+node.getKey());
                    System.out.print("--->"+node.getValue());

                    return node;
                }
                return null;
            }


        }
        return null;
    }
    //节点删除
    public void delNode(String k){  //调用查找函数，删除最底层的某个节点，并把其节点的左右相连，和链表操作一样，只是其上方若有则都需要调整
        Node temp=find(k);
        while(temp!=null){
            temp.getLeft().setRight(temp.getRight());
            temp.getRight().setLeft(temp.getLeft());
            temp=temp.getUp();
        }
    }
    public void print(){
        Node node;
        Node node1=head;


        while(node1!=null){
            int k=0;
            node=node1;
            while(node!=null){
                System.out.print(node.getKey()+"\t");
                k++;
                node=node.getRight();
            }

            System.out.print("\t");
            System.out.print("("+k+")");
            //System.out.print(node.getKey());
            System.out.println();
            //node=node1.getDown();
            node1=node1.getDown();

        }
    }

}
class Node{
    public String key;
    public int value;
    public Node up, down,left , right;
    public static String tou=new String("--头--");
    public static String wei=new String("--尾--");
    public Node(String k, int v){
        this.key=k;
        this.value=v;
        up=down=left=right=null;
    }
    public void setUp(Node up){
        this.up=up;
    }
    public Node getUp(){
        return up;
    }
    public void setDown(Node down){
        this.down=down;
    }
    public Node getDown(){
        return down;
    }
    public void setLeft(Node left){
        this.left=left;
    }
    public Node getLeft(){
        return left;
    }
    public void setRight(Node right){
        this.right=right;
    }
    public Node getRight(){
        return right;
    }
    public void setKey(String k){
        this.key=k;
    }
    public String getKey(){
        return key;
    }
    public void setValue(int v){
        this.value=v;
    }
    public int getValue(){
        return value;
    }

}



//测试类
package com;

public class Test {
    public static void main(String[] args){
        SkipList s = new SkipList();
//      s.add("AAA", 122);
        int i=0;
        for(;i<30;i++){ //随机数字进行测试
            s.add(String.valueOf(i), i);
        }
        s.print();
        System.out.println("\n\n----------\n\n\n");
        if(s.find("22")!=null){ //查找
            System.out.println("\nOK");
        }else{//找不到
            System.out.println("\nfalse");

        }
        s.delNode("0"); //删除
        s.print();
    }
}

整数集合

用于集合中的元素都为整数且元素不多。
结构

public class IntSetStruts {
    //编码
    Long encoding;
    //长度
    Long length;
    //存储容器
    Long contents[];
}

因为有16位。32位。64位的长度所以如果都用64位来存储会造成浪费因此有编码这个字段会生存储空间。
压缩列表
对这个没有太大的兴趣请参考博文
https://blog.csdn.net/men_wen/article/details/70176753