redis的数据结构

string:

实现类似于java的ArrayList，当串大小小于1MB时候，采用加倍扩容，当大于1MB时，则每次扩容只会多扩容1MB的空间，最大长度为512MB

相关指令：set key value get key mset key1 value1 key2 value2...keyn valuen mget key1..keyn setnx key value等

list:

实现类似于java的LinkedList，是双指针结构，但并不是常规的linkedlist，而是一个快速链表的结构，当元素比较少时候，分配一块连续的内存空间，使用ziplist压缩列表，当数据量比较多的时候，改为快速链表，快速链表通过把原来的linkedlist分割成一段段用ziplist存储，并把ziplist连接起来，由于定位速度相对较慢，插入删除比较快，适合对端操作如异步队列、栈等

相关指令： lpush lpop rpush rpop llen lindex ltrim等

hash(字典):

类似于hashMap，采用链地址法解决hash冲突，hash的值只能为字符串，rehash采用渐进式策略，rehash同时，会保留新旧两个hash结构，当查询时，会查询两个hash结构，搬迁完成时，旧的hash结构会被删除

相关指令 hset hgetall hlen hget hmset等

set:

hashset 特殊的字典,value为NULL值，去重

相关指令： sadd smembers  sismember scard spop

zset(有序列表):

类似于TreeMap，具有排序功能，使用跳表，具有多层索引的数据结构实现，zset中最后一个value被移除后，结构会被删除并回收内存

相关指令：zadd zrange zrevrange zcard zscore zrangebyscore zrem zrange

bitmap(位图):

位图相当于一个byte数组，每个bit取值只能为0或者1，如果某个偏移位置超出现有内容的范围，会进行零扩充，简单的例子

HyperLogLog

这个数据结构提供不太精确的去重计数方案，标准误差为0.81%，但对于统计大量数据来说，对比其他数据结构十分节省空间，用于解决精确度不是很高的统计问题比如统计某个页面的uv，实现比较复杂详细介绍

相关指令：pfadd pfcount pfmerge

BloomFilter 布隆过滤器

布隆过滤器可以理解为不太精确的set，它通过将一个key的hash值分布到一个大的bit数组上面，判断一个key是否存在时只需判断该的hash对应的bit位是否都是1，如果全是1则表示存在，否则不存在。性能相对较高并节省空间，但对于原先不存在的元素可能在判断时候存在误判比如对应的bit位刚好被其他的key置为1了

redis官方在4.0后以插件https://github.com/RedisBloom/RedisBloom的形式加载到redis server上去，而java方面的使用也可以使用JReBloomhttps://github.com/redisbloom/JReBloom来对应操作代码，但这里采用操作bitmap来实现布隆过滤器，模仿（大部分copy）guava的bloomfilter来实现

操作位图的接口

package com.gdut.imis.orderfood.bloomfilter;

/**
 * @author: lele
 * @date: 2019/12/20 上午11:31
 */
public interface BitArray<T> {
    void setBitSize(long bitSize);

    boolean set(long index);

    boolean setBatch(long[] index);

    boolean get(long index);

    boolean getBatch(long[] index);

    long bitSize();
}

redis的位图操作实现类，这里使用redistemplate+pipline操作

package com.gdut.imis.orderfood.bloomfilter;


import org.springframework.data.redis.core.RedisCallback;
import org.springframework.data.redis.core.RedisTemplate;

import java.util.List;

/**
 * @author: lele
 * @date: 2019/12/20 上午11:39
 * 操作redis的bitset
 */
public class RedisTemplateBitArray implements BitArray {


    private RedisTemplate redisTemplate;

    private String key;

    private long bitSize;

    /**
     * 2^32
     */
    public static final long MAX_REDIS_BIT_SIZE = 4_294_967_296L;

    public static final String KEY_PREFIX = "bloom_filter:";


    public RedisTemplateBitArray(RedisTemplate redisTemplate, String key) {
        this.redisTemplate = redisTemplate;
        this.key = KEY_PREFIX + key;
    }


    @Override
    public void setBitSize(long bitSize) {
        if (bitSize > MAX_REDIS_BIT_SIZE) {
            throw new IllegalArgumentException("Invalid redis bit size, must small than 2 to the 32");
        }
        this.bitSize = bitSize;
    }

    @Override
    public boolean set(long index) {
        boolean result;
        result = (boolean) redisTemplate.execute((RedisCallback) redisConnection -> redisConnection.setBit(key.getBytes(), index, true).booleanValue());
        return result;
    }

    @Override
    public boolean setBatch(long[] index) {
        redisTemplate.executePipelined((RedisCallback) redisConnection -> {
            redisConnection.openPipeline();
            for (long l : index) {
                redisConnection.setBit(key.getBytes(), l, true);
            }
            return null;
        });
        return Boolean.TRUE;
    }

    @Override
    public boolean get(long index) {
        boolean result;
        result = (boolean) redisTemplate.execute((RedisCallback) redisConnection -> redisConnection.getBit(key.getBytes(), index));
        return result;
    }

    @Override
    public boolean getBatch(long[] index) {
        return !redisTemplate.executePipelined((RedisCallback<List<Boolean>>) redisConnection -> {
            redisConnection.openPipeline();
            for (long l : index) {
                //如果其中一个没有，那就是没有
                redisConnection.getBit(key.getBytes(), l);
            }
            return null;
        }).contains(Boolean.FALSE);

    }


    @Override
    public long bitSize() {
        return this.bitSize;
    }
}

bloomfiter类

package com.gdut.imis.orderfood.bloomfilter;

import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;

import java.util.function.Consumer;
import java.util.function.Function;

/**
 * @author: lele
 * @date: 2019/12/20 上午11:35
 */
public class CustomBloomFilter<T> {
    interface Strategy {
        <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits, boolean batch);

        <T> boolean mightContain(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits, boolean batch);

        /**
         * 批量添加使用
         *
         * @param consumer
         * @param value
         * @return
         */
        static boolean batchAdd(Consumer<Long> consumer, long[] value) {
            for (long l : value) {
                consumer.accept(l);
            }
            return Boolean.TRUE;
        }

        /**
         * 批量获取使用
         *
         * @param function
         * @param value
         * @return
         */
        static boolean batchGet(Function<Long, Boolean> function, long[] value) {
            for (long l : value) {
                if (!function.apply(l)) {
                    return Boolean.FALSE;
                }
            }
            return Boolean.TRUE;
        }
    }

    /**
     * 操作位图的接口
     */
    private final BitArray bits;

    /**
     * hash函数个数k
     */
    private final int numHashFunctions;
    /**
     * 将传入的实例转换基本类型 char,int,long,byte
     */
    private final Funnel<? super T> funnel;

    /**
     * hash策略
     */
    private final Strategy strategy;

    /**
     * 自定义属性，批量操作
     */
    private final Boolean batch;


    /**
     * expectedInsertions 期望插入元素的个数
     * fpp 错误率
     */
    public static <T> CustomBloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy, BitArray bits, Boolean batch) {
        Preconditions.checkArgument(
                expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
        Preconditions.checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
        Preconditions.checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
        Preconditions.checkNotNull(strategy);

        if (expectedInsertions == 0) {
            expectedInsertions = 1;
        }

        long numBits = optimalNumOfBits(expectedInsertions, fpp);
        bits.setBitSize(numBits);
        int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
        return new CustomBloomFilter<>(bits, numHashFunctions, funnel, strategy, batch);
    }


    public static <T> CustomBloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BitArray bitArray) {
        return create(funnel, expectedInsertions, fpp, CustomBloomFilterStrategies.MURMUR128_MITZ_64, bitArray, Boolean.TRUE);
    }

    public static <T> CustomBloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, BitArray bitArray) {
        return create(funnel, expectedInsertions, 0.03, CustomBloomFilterStrategies.MURMUR128_MITZ_64, bitArray, Boolean.TRUE);
    }

    public static <T> CustomBloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, BitArray bitArray, Boolean batch) {
        return create(funnel, expectedInsertions, 0.03, CustomBloomFilterStrategies.MURMUR128_MITZ_64, bitArray, batch);
    }

    private CustomBloomFilter(BitArray bits,
                              int numHashFunctions,
                              Funnel<? super T> funnel,
                              Strategy strategy,
                              Boolean batch) {
        this.bits = bits;
        this.numHashFunctions = numHashFunctions;
        this.strategy = strategy;
        this.funnel = funnel;
        this.batch = batch;
    }

    public boolean mightContain(T object) {
        return strategy.mightContain(object, funnel, numHashFunctions, bits, batch);
    }


    public void put(T object) {
        strategy.put(object, funnel, numHashFunctions, bits, batch);
    }

    static int optimalNumOfHashFunctions(long n, long m) {
        // (m / n) * log(2), but avoid truncation due to division!
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }

    static long optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

}

哈希策略

package com.gdut.imis.orderfood.bloomfilter;

import com.baomidou.mybatisplus.extension.api.R;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;
import com.google.common.primitives.Longs;

import java.util.function.Consumer;
import java.util.function.Function;

/**
 * @author: lele
 * @date: 2019/12/20 上午11:39
 * 沿用guava的hash方法
 */
public enum CustomBloomFilterStrategies implements CustomBloomFilter.Strategy {


    MURMUR128_MITZ_64 {
        @Override
        public <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bitArray, boolean batch) {
            long bitSize = bitArray.bitSize();
            byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).asBytes();
            long[] indexs = getIndex(bytes, numHashFunctions, bitSize);
            return batch ? bitArray.setBatch(indexs) : CustomBloomFilter.Strategy.batchAdd(e -> bitArray.set(e), indexs);
        }

        @Override
        public <T> boolean mightContain(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bitArray, boolean batch) {
            long bitSize = bitArray.bitSize();
            byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).asBytes();
            long[] indexs = getIndex(bytes, numHashFunctions, bitSize);
            return batch ? bitArray.getBatch(indexs) : CustomBloomFilter.Strategy.batchGet(e -> bitArray.get(e), indexs);
        }

        private long lowerEight(byte[] bytes) {
            return Longs.fromBytes(bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]);
        }

        private long upperEight(byte[] bytes) {
            return Longs.fromBytes(bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]);
        }


        private long[] getIndex(byte[] bytes, int numHashFunctions, long bitSize) {
            long hash1 = this.lowerEight(bytes);
            long hash2 = this.upperEight(bytes);
            long combinedHash = hash1;
            long[] batchIndex = new long[numHashFunctions];
            for (int i = 0; i < numHashFunctions; ++i) {
                batchIndex[i] = (combinedHash & 9223372036854775807L) % bitSize;
                combinedHash += hash2;
            }
            return batchIndex;
        }
    },
    MURMUR128_MITZ_32() {
        @Override
        public <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bitArray, boolean batch) {
            long bitSize = bitArray.bitSize();
            long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
            long[] indexs = getIndex(hash64, numHashFunctions, bitSize);
            return batch ? bitArray.setBatch(indexs) : CustomBloomFilter.Strategy.batchAdd(e -> bitArray.set(e), indexs);

        }

        @Override
        public <T> boolean mightContain(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bitArray, boolean batch) {
            long bitSize = bitArray.bitSize();
            long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
            long[] indexs = getIndex(hash64, numHashFunctions, bitSize);
            return batch ? bitArray.getBatch(indexs) : CustomBloomFilter.Strategy.batchGet(e -> bitArray.get(e), indexs);

        }

        long[] getIndex(long hash64, int numHashFunctions, long bitSize) {
            int hash1 = (int) hash64;
            int hash2 = (int) (hash64 >> 32);
            long[] batchIndex = new long[numHashFunctions];
            //根据传进的hash函数个数来确定进行多少次hash计算
            for (int i = 1; i <= numHashFunctions; i++) {
                int combinedHash = hash1 + (i * hash2);
                if (combinedHash < 0) {
                    combinedHash = ~combinedHash;
                }
                batchIndex[i - 1] = combinedHash % bitSize;
            }
            return batchIndex;
        }
    }


}

@Test
   public void testBloom(){
       RedisTemplateBitArray array=new RedisTemplateBitArray(redisTemplate,"test");
       CustomBloomFilter<String> bloomFilter = CustomBloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 1000,  array);
       String testElement1 = "hi";
       String testElement2 = "hello";
       String testElement3 = "789";
       bloomFilter.put(testElement1);
       bloomFilter.put(testElement2);
       System.out.println(bloomFilter.mightContain(testElement1));
       System.out.println(bloomFilter.mightContain(testElement2));
       System.out.println(bloomFilter.mightContain(testElement3));
   }

Geo 地理位置

实现其实是一个zset结构，可以用来获取两点之间的距离，获取一定范围内的地理位置比如附近门店,附近的人等等，简单的理解的话，他是使用geohash算法，它将二位的经纬度数据映射到一维的点，变成一个整数，score就是使用geohash进行处理后的值，通过排序可以获得对应坐标的附近元素

geoadd添加key对应member的经纬度

可以用zrem key member删除对应的成员

获取两点的距离

获取经纬度或者hash值，hash值可以去http://geohash.org去查

根据现有成员获取对应的自己及其他成员位置信息

根据给定的经纬度获取

基于redisTemplate部分代码实现:

GeoOperations<String, String> stringStringGeoOperations = redisTemplate.opsForGeo();
        Point point =new Point(113.3261100000,23.1438700000);
        Point point2 =new Point(113.3620000000,23.1959400000);
        Point point3 =new Point(113.3199356300,23.1450263200);
        stringStringGeoOperations.add("location_store_list",point,"海航");
        stringStringGeoOperations.add("location_store_list",point2,"龙洞");
        stringStringGeoOperations.add("location_store_list",point3,"中信的麦当劳");
        double value = stringStringGeoOperations.distance("location_store_list", "海航", "龙洞",RedisGeoCommands.DistanceUnit.KILOMETERS).getValue();
        System.out.println(value);
        Point here = new Point(113.3246700000,23.1421130000);
        Distance distance=new Distance(100, Metrics.KILOMETERS);
        Circle circle=new Circle(here,distance);
        RedisGeoCommands.GeoRadiusCommandArgs args=RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs()
                .includeDistance().includeCoordinates().sortAscending().limit(3);
        GeoResults<RedisGeoCommands.GeoLocation<String>> store_list = stringStringGeoOperations.radius("location_store_list", circle, args);
        for (GeoResult<RedisGeoCommands.GeoLocation<String>> geoLocationGeoResult : store_list) {
            double resDistance = geoLocationGeoResult.getDistance().getValue();
            String name = geoLocationGeoResult.getContent().getName();
            Point point1 = geoLocationGeoResult.getContent().getPoint();
            System.out.printf("name:%s,distance:%s,x:%s,y:%s%n",name,resDistance,point1.getX(),point1.getY());
        }