精华内容
下载资源
问答
  • 哈希算法用途

    千次阅读 2019-05-25 21:35:44
    什么是哈希算法 一说到哈希算法, 我瞬间就想到了哈希函数、哈希表, 其实他们并不是一回事. 简单来说, 哈希算法就是将任意长度的字符串通过计算转换为固定长度的字符串, 不对, 不光字符串, 应该说是将任意长度的二...

    什么是哈希算法

    一说到哈希算法, 我瞬间就想到了哈希函数、哈希表, 其实他们并不是一回事.

    简单来说, 哈希算法就是将任意长度的字符串通过计算转换为固定长度的字符串, 不对, 不光字符串, 应该说是将任意长度的二进制串转换为固定长度的二进制串, 这个转换的过程就是哈希算法.

    既然将任意长度的字符串转换成固定长度的, 那么冲突就不可避免了, 比如将0-100所有的数字, 映射到0-10这十个数字上, 难免会发生冲突. 一般来说, 计算得出的哈希值越长, 冲突的概率就越低, 比如说, 计算过后, 哈希值为16个字节, 也就是128位, 那么就有2^128个不同的哈希值, 发生哈希冲突的概率为(1/2)^128, 这个概率可以说很低了.

    以MD5为例, 以下是经过MD5转换后的值:

    朋友你好: 677fe16950241e74ef632efb2b9f92a7

    朋友你好!: 6efa551df87d9de987f17be4e73eb720

    可以看到, 哪怕仅仅差了一个感叹号, 计算后的值也是天壤之别, 所以很多网站上下载文件的同时还提供md5值, 现在能够理解了吧, 你将下载后的文件通过md5算法进行计算, 得到的字符串如果和网站给定的不相同, 说明文件被修改过了.

    当然, 哈希算法不仅仅只有md5这一种, 以用途来分析哈希算法, 就不说哈希算法的原理了, 因为我不会.

    1. 数据校验

    上面说到的md5就是其中的一个, 好像还有一个什么SHA, 不过我不知道, 也就不展开探讨了.

    md5可以将一个文件经过计算转换成一个指定长度的字符串, 可以防止文件被篡改, 但是通过加密后的字符串很难逆向推出原文.

    前面那个例子可以看到, 即使文件被修改了一点点, 也会导致计算后的值发生很大变换.

    2.唯一标识

    比如说, 现在有十万个文件, 给你一个文件, 要你在这十万个文件中查找是否存在. 一个很笨的办法就是把每一文件都拿出来, 然后按照二进制串一一进行对比. 但是这个操作注定是比较费时的.

    可以用哈希算法对文件进行计算, 然后比较哈希值是否相同. 因为存在哈希冲突的情况, 你可以在相同哈希值的文件再进行二进制串比较.

    3.哈希表

    在哈希表中使用哈希函数已经并不陌生了, 不再赘述.

    4.负载均衡

    比如说, 现在又多台服务器, 来了一个请求, 如何确定这个请求应该路由到哪个路由器呢?当然, 必须确保相同的请求经过路由到达同一个服务器. 一种办法就是保存一张路由关系的表, 比如客户端IP和服务器编号的映射, 但是如果客户端很多, 势必查找的时间会很长. 这时, 可以将客户端的唯一标识信息(如:IP、username等)进行哈希计算, 然后与服务器个数取模, 得到的就是服务器的编号.

    5.分布式存储

    当我们有大量数据时, 一般会选择将数据存储到多个服务器, 为了提高读取与写入的速度嘛. 决定将文件存储到哪台服务器, 就可以通过哈希算法取模的操作来得到.

    但是, 如果数据多了, 要增加服务器了, 问题就来了, 比如原来是10台服务器, 现在变成15台了, 那么原来哈希值为16的文件被分配到编号6的服务器, 现在被分配到编号1的服务器, 也就意味着所有文件都要重新计算哈希值并重新非陪服务器进行存储. 一致性哈希就是这个用途, 可以查找我的历史文章.

    暂时我能想到的就只有这些, 当然, 哈希算法的用途还有很多, git中的commit id等, 但是我不太了解, 就假装没有吧, 嘿嘿


    有时对用户的密码进行MD5加密再保存, 确实要比明文保存好的多. 但是, 你以为通过哈希算法进行加密就万事大吉了么? 不好意思, 并不能, 像前面提到的MD5就已经号称别破解了.

    比如, 你将用户的密码进行MD5加密后进行保存, 若有心人拿到你的数据库数据, 虽然得到的是加密后的密码, 但是只要准备一个常用密码的字典, 将字典中的密码进行加密后与数据库保存的数据进行比较, 如果相同, 基本上就可以确定了.

    我感觉可以对密码进行双层加密, 也就是使用两个不同的加密算法, 一个算法的输出作为另一个的输入, 增大一些破解的难度吧.

    再见!!!

    展开全文
  • 一、一致性哈希算法

    2020-07-05 10:57:53
    1 一致性哈希算法用途 2 一致性哈希算法介绍 3 一致性哈希算法实现 3.1 排序算法+二分查找 3.2 直接遍历 3.3 二叉查找树 4 TreeMap实现一致性哈希 4.1 红黑树介绍 4.2 哈希再计算 4.3 一致性哈希算法代码...

    目录

     

    1 一致性哈希算法用途

    2 一致性哈希算法介绍

    3 一致性哈希算法实现

    3.1 排序算法+二分查找

    3.2 直接遍历

    3.3 二叉查找树

    4 TreeMap实现一致性哈希

    4.1 红黑树介绍

    4.2 哈希再计算

    4.3 一致性哈希算法代码实现

    4.4 一致性哈希算法优化(虚拟节点)


    1 一致性哈希算法用途

    一致性哈希是解决上线、下线后相同的请求尽可能的命中原来服务器的问题。
    假如我们自己设计了一个高可用缓存系统,可以集群部署,那么我们每个节点上应该怎样分配数据呢?
    假如说我们存放一个k-v数据,这个数据需要怎么确定存放节点?常用的方式是用key的哈希值对服务器节点取模,这样实现比较简单,但是带来的问题就是缓存系统上线、下线节点后原来节点缓存的数据命中率打打大大降低。
    三个节点的路由表
    哈希值    0    1    2    3    4    5    6    7    8    9    10    11    12    13    14
    路由        0    1    2    0    1    2    0    1    2    0    1       2      0     1      2
    四个节点的路由表
    哈希值    0    1    2    3    4    5    6    7    8    9    10    11    12    13    14
    路由        0    1    2    3    0    1    2    3    0    1     2      3      0      1      2
    可以看到只有6个哈希值在可以路要到原来的服务器,其余的缓存都不能命中。这样带来的直接后果是
    1 可能可能会带来类似缓存雪崩的影响。缓存雪崩是指缓存数据大批量到过期时间,而查询数据量巨大,引起数据库压力过大甚至宕机。
    2 节点中大量无法命中的数据过期之前还在占用内存。

    2 一致性哈希算法介绍

    为了更好地提升缓存系统的伸缩性需要设计一个可靠的一致性哈希算法。
    一致性哈希算法是构建一个哈希环来实现key到节点的映射。我们定义一个哈希环如下结构(0,1,2三个节点哈希值分别是0,5,10),每个节点是每个缓存系统的哈希值
    0->5->10->0
    路由规则是每个key落到刚好比它哈希值大的节点上。如果这个key大于环上所有的哈希值那么就落在最小的哈希节点
    三个节点的路由表
    哈希值    0    1    2    3    4    5    6    7    8    9    10    11    12    13    14
    路由        1    1    1    1    1    2    2    2    2    2    0      0      0      0      0
    这个时候我们增加了一个节点,哈希值是12,那么新的哈希环如下
    0->5->10->12->0
    四个节点的路由表
    哈希值    0    1    2    3    4    5    6    7    8    9    10    11    12    13    14
    路由        1    1    1    1    1    2    2    2    2    2    3      3      0      0      0
    这个时候我们看到只有两个哈希值没有路由到原来的节点,服务扩容后只会影响新增服务下一个节点的缓存路由,很好的解决了取模路由暴露的两个两个问题。

    3 一致性哈希算法实现

    3.1 排序算法+二分查找

    最优的排序算法时间复杂度是O(NlogN),二分查找算法时间复杂度是O(logN),所以这种方式的时间复杂度取决于耗时较长的排序算法,即O(NlogN)

    3.2 直接遍历

    这种方式比较简单,时间复杂度是O(N)

    3.3 二叉查找树

    二叉查找树的优点是查找效率高,时间复杂度是Olog(N),缺点是建树过程比较耗性能。不过考虑到服务上下线场景比较有限,这个缺点可以忽略,下面我们就以二叉查找树为例来实现一致性哈希算法

    4 TreeMap实现一致性哈希

    4.1 红黑树介绍

    满足以下特征的树就是红黑树
    1. 节点是红色或者黑色
    2. 根节点是黑色
    3. 每个叶子的节点都是黑色的空节点(NULL)
    4. 每个红色节点的两个子节点都是黑色的。
    5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。
    这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。


    TreeMap就是红黑树的实现。

    4.2 哈希再计算

    我们看一下调用String默认的哈希算法计算节点ip的哈希值
    127.0.0.1:8080->127.0.0.1:8084

    @Test
    public void testStringHash() {
        // 5个server服务器
        for (int i = 0; i < 5; i ++) {
            String server = "127.0.0.1:808" + i;
            System.out.println(server + "->" + server.hashCode());
        }
    }

    输出:
    127.0.0.1:8080->-35736627
    127.0.0.1:8081->-35736626
    127.0.0.1:8082->-35736625
    127.0.0.1:8083->-35736624
    127.0.0.1:8084->-35736623
    可以看到这种方式计算的结果,哈希值根本散不开
    重新计算Hash值的算法有很多,可以参考https://blog.csdn.net/whut_gyx/article/details/39002191了解下
    这里我们采用散列效果和性能都不错的FNV1_32_HASH算法

    private int fnv32Hash(String str) {
        final int p = 16777619;
        int hash = -2128831035;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash ^ str.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
    
        // 如果算出来的值为负数则取其绝对值
        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }

    测试代码

    @Test
    public void testFnv32Hash() {
        // 5个server服务器
        for (int i = 0; i < 5; i ++) {
            String server = "127.0.0.1:808" + i;
            System.out.println(server + "->" + fnv32Hash(server));
        }
    }

    输出:
    127.0.0.1:8080->1617490351
    127.0.0.1:8081->674407738
    127.0.0.1:8082->1511613106
    127.0.0.1:8083->1255419186
    127.0.0.1:8084->265259256
    可以看到散列效果还是不错的

    4.3 一致性哈希算法代码实现

    // key list
    private List<String> keyList;
    
    // 缓存服务器ip集合
    private List<String> serverList;
    
    // 缓存服务器构建的二叉树
    private SortedMap<Integer, String> sortedMap = new TreeMap<>();
    @Before
    public void init() {
        // 100个key
        keyList = new ArrayList<>();
        for (int i = 0; i < 100; i ++) {
            keyList.add("key" + i);
        }
    
        // 5个server服务器
        serverList = new ArrayList<>();
        for (int i = 0; i < 5; i ++) {
            serverList.add("127.0.0.1:808" + i);
        }
    }
    
    // 获取key路由到的服务器
    private String getServer(String key) {
        // 得到带路由的结点的Hash值
        int hash = fnv32Hash(key);
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap.size() <= 0) {
            subMap = sortedMap;
        }
        // 第一个Key就是顺时针过去离node最近的那个结点
        Integer i = subMap.firstKey();
        // 返回对应的服务器名称
        return subMap.get(i);
    
    }
    
    
    private int fnv32Hash(String str) {
        final int p = 16777619;
        int hash = -2128831035;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash ^ str.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
    
        // 如果算出来的值为负数则取其绝对值
        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }

    测试代码:

    @Test
    public void testConsistentHash() {
        for (String server : serverList) {
            int hash = fnv32Hash(server);
            System.out.println("[" + server + "]加入集合中, 其Hash值为" + hash);
            sortedMap.put(hash, server);
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String key : keyList) {
            String server = getServer(key);
            List<String> list = map.get(server);
            if (Objects.isNull(list)) {
                list = new ArrayList<>();
                map.put(server, list);
            }
            list.add(key);
        }
        map.forEach((k, v) -> System.out.println(k + "->" + v.size() + ":" + v));
    }

    输出:
    [127.0.0.1:8080]加入集合中, 其Hash值为1617490351
    [127.0.0.1:8081]加入集合中, 其Hash值为674407738
    [127.0.0.1:8082]加入集合中, 其Hash值为1511613106
    [127.0.0.1:8083]加入集合中, 其Hash值为1255419186
    [127.0.0.1:8084]加入集合中, 其Hash值为265259256
    127.0.0.1:8081->12:[key13, key19, key30, key49, key61, key63, key64, key70, key72, key92, key95, key98]
    127.0.0.1:8082->11:[key0, key10, key21, key34, key39, key45, key51, key60, key81, key86, key96]
    127.0.0.1:8080->8:[key4, key14, key43, key44, key56, key84, key87, key89]
    127.0.0.1:8083->27:[key6, key7, key9, key11, key20, key25, key26, key27, key28, key33, key40, key41, key42, key46, key47, key52, key55, key65, key67, key71, key74, key77, key78, key90, key91, key93, key97]
    127.0.0.1:8084->42:[key1, key2, key3, key5, key8, key12, key15, key16, key17, key18, key22, key23, key24, key29, key31, key32, key35, key36, key37, key38, key48, key50, key53, key54, key57, key58, key59, key62, key66, key68, key69, key73, key75, key76, key79, key80, key82, key83, key85, key88, key94, key99]

    4.4 一致性哈希算法优化(虚拟节点)

    上述代码一致性哈希算法我们可以看到每个key可以被正确路由到对应的节点,但是有另一个问题,分配不均。我们看到分配最少缓存的节点上只有8个缓存,最多缓存节点上有42个缓存
    解决这个问题的办法是引入虚拟节点,其工作原理是:将一个物理节点拆分为多个虚拟节点,并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。采取这样的方式,就可以有效地解决增加或减少节点时候的负载不均衡的问题。
    带有虚拟节点的一致性哈希算法实现

    @Test
    public void testConsistentVirtualHash() {
        List<String> virtualServerList = new ArrayList<>();
        // 每个server虚拟5个地址
        int virtualServerCount = 5;
        for (String server: serverList) {
            for (int i = 0; i < virtualServerCount; i ++) {
                String virtualServer = server + "@VN" + i;
                virtualServerList.add(virtualServer);
            }
        }
        for (String virtualServer : virtualServerList) {
            int hash = fnv32Hash(virtualServer);
            System.out.println("[" + virtualServer + "]加入集合中, 其Hash值为" + hash);
            sortedMap.put(hash, virtualServer);
        }
    
        Map<String, List<String>> map = new HashMap<>();
        for (String key : keyList) {
            String virtualServer = getServer(key);
            // 解析出真正的ip
            String realServer = virtualServer.split("@")[0];
            List<String> list = map.get(realServer);
            if (Objects.isNull(list)) {
                list = new ArrayList<>();
                map.put(realServer, list);
            }
            list.add(key);
        }
        map.forEach((k, v) -> System.out.println(k + "->" + v.size() + ":" + v));
    }

    输出
    [127.0.0.1:8080@VN0]加入集合中, 其Hash值为1653752734
    [127.0.0.1:8080@VN1]加入集合中, 其Hash值为2045770422
    [127.0.0.1:8080@VN2]加入集合中, 其Hash值为642460142
    [127.0.0.1:8080@VN3]加入集合中, 其Hash值为2064903931
    [127.0.0.1:8080@VN4]加入集合中, 其Hash值为134338595
    [127.0.0.1:8081@VN0]加入集合中, 其Hash值为1207025989
    [127.0.0.1:8081@VN1]加入集合中, 其Hash值为1416458113
    [127.0.0.1:8081@VN2]加入集合中, 其Hash值为2109124764
    [127.0.0.1:8081@VN3]加入集合中, 其Hash值为487588720
    [127.0.0.1:8081@VN4]加入集合中, 其Hash值为887324084
    [127.0.0.1:8082@VN0]加入集合中, 其Hash值为27662755
    [127.0.0.1:8082@VN1]加入集合中, 其Hash值为1353238534
    [127.0.0.1:8082@VN2]加入集合中, 其Hash值为1234344991
    [127.0.0.1:8082@VN3]加入集合中, 其Hash值为1502278984
    [127.0.0.1:8082@VN4]加入集合中, 其Hash值为1362517544
    [127.0.0.1:8083@VN0]加入集合中, 其Hash值为1128722563
    [127.0.0.1:8083@VN1]加入集合中, 其Hash值为1998095489
    [127.0.0.1:8083@VN2]加入集合中, 其Hash值为2077514034
    [127.0.0.1:8083@VN3]加入集合中, 其Hash值为1266869294
    [127.0.0.1:8083@VN4]加入集合中, 其Hash值为842010729
    [127.0.0.1:8084@VN0]加入集合中, 其Hash值为263233063
    [127.0.0.1:8084@VN1]加入集合中, 其Hash值为1695356940
    [127.0.0.1:8084@VN2]加入集合中, 其Hash值为956902
    [127.0.0.1:8084@VN3]加入集合中, 其Hash值为2050272550
    [127.0.0.1:8084@VN4]加入集合中, 其Hash值为1840275863
    127.0.0.1:8081->11:[key7, key9, key42, key47, key59, key61, key64, key67, key70, key71, key99]
    127.0.0.1:8082->8:[key0, key21, key39, key45, key60, key79, key81, key96]
    127.0.0.1:8080->31:[key3, key4, key10, key12, key13, key14, key19, key22, key23, key24, key30, key31, key34, key43, key44, key49, key50, key51, key54, key56, key57, key63, key66, key72, key73, key82, key84, key86, key87, key89, key98]
    127.0.0.1:8083->30:[key5, key6, key8, key11, key17, key18, key20, key25, key26, key27, key28, key33, key38, key40, key41, key46, key52, key55, key65, key74, key77, key78, key85, key90, key91, key92, key93, key94, key95, key97]
    127.0.0.1:8084->20:[key1, key2, key15, key16, key29, key32, key35, key36, key37, key48, key53, key58, key62, key68, key69, key75, key76, key80, key83, key88]
    可以看到我们虚拟5个节点后分配最少缓存的节点上只有8个缓存,最多缓存节点上有31个缓存,提高了缓存分配均衡性

    展开全文
  • 哈希算法

    千次阅读 2017-09-10 19:14:39
    本文详细地介绍了哈希算法的原理和用途,并提供3种将关键字转换为哈希值和2种解决位置冲突的方法的原理和实现过程,同时提供算法的实现源码和测试结果

    1 哈希表的原理和用途

    哈希表是基于数组来实现,它提供了快速的插入操作和查找操作。在初始阶段插入的数据量较少时,插入、删除和查找只需接近常量时间,即时间复杂度为0(1)。如果不需要有序遍历数据,并且可以提前预测数据量的大小,那么哈希表在的性价比是最佳的。缺点是基于数组,后续拓展比较困难,某些哈希表快填满时候,性能下降的非常严重。


    2 哈希化

    2.1 常用的哈希化方法

    将关键字通过哈希函数转换为数组下标,这个过程称为哈希化。




    2.2 三种方法的实现代码

    public class HashTable {
    /**
    * 哈希表的底层是数组
    */
    private Employee[] arr;
    
    /**
    * 默认的构造方法
    */
    public HashTable() {
    arr = new Employee[100];
    }
    
    /**
    * 
    * @param maxsize
    */
    public HashTable(int maxsize) {
    arr = new Employee[maxsize];
    }
    
    /**
    * 插入数据
    * @param emp
    */
    public void insert(Employee emp){
    arr[hashCode(emp.getKey())] = emp;
    }
    
    /**
    * 查找数据
    * @param key
    * @return
    */
    public Employee find(String key){
    return arr[hashCode(key)];
    }
    
    /**
    * 获取哈希值
    * 方法1:数字相加
    * SCII码从0到255,可以容纳字母和标点符号等字符,其中0是48,依次递增,9是57;
    * @param key
    * @return
    */
    /*public int hashCode(String key){
    int hashVal = 0;
    for(int i = key.length() - 1; i >=0; i--){
    int letter = key.charAt(i) - 48;
    hashVal += letter;
    }
    return hashVal;
    }*/
    
    /**
    * 获取哈希值
    * 方法2:幂的连乘
    * @param key
    * @return
    */
    /*public int hashCode(String key){
    int hashVal = 0;
    int pow10 = 1;
    for(int i = key.length() - 1; i >=0; i--){
    int letter = key.charAt(i) - 48;
    hashVal += letter * pow10;
    pow10 *= 10;
    }
    return hashVal;
    }*/
    
    /**
    * 获取哈希值
    * 方法3:去余操作
    * @param key
    * @return
    */
    public int hashCode(String key){
    //考虑数组太大时溢出的情况
    /*BigInteger hashVal = new BigInteger("0") ;
    BigInteger pow10 = new BigInteger("1") ;
    for(int i = key.length() - 1; i >=0; i--){
    int letter = key.charAt(i) - 48;
    BigInteger letterB = new BigInteger(String.valueOf(letter));
    hashVal = hashVal.add(letterB.multiply(pow10));
    pow10 = pow10.multiply(new BigInteger(String.valueOf(10)));
    }
    //取余数
    return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();*/
    
    int hashVal = 0;
    int pow10 = 1;
    for(int i = key.length() - 1; i >=0; i--){
    int letter = key.charAt(i) - 48;
    hashVal += letter * pow10;
    pow10 *= 10;
    }
    //取余
    return hashVal % arr.length;
    }
    }


    3 开发放地址法

    3.1原理

    当冲突发生时,通过查找数组的一个空位,并将数据填入,而不再用哈希函数得到的数组下标。根据查找空位时使用的方法可细分为线性探测法,二次探测法和再哈希法三种。

    3.2线性探测法

    3.2.1原理

    如果要插入的1000位置已满,则查找1001,若还是满的,则查找1002,依次类推直到找到空位为止。缺点:当增加越来越多的数据项时,填充序列(一串连续的已填充单元)变的越来越长,性能下降,即发生原始聚集。


    3.2.2完整代码

    public class Student {
    /**
    * 学号
    */
    private String stuNo;
    
    
    /**
    * 有参构造函数
    * @param stuNo
    */
    public Student(String stuNo) {
    this.stuNo = stuNo;
    }
    
    /**
    * 获取关键字
    * @return
    */
    public String getKey(){
    return stuNo;
    }
    }
    
    
    package openaddressing;
    
    
    /**
     * @author JayLai
     * @date 2017年8月30
     * @descriptions:开放地址法,线性探测
     * @version 1.0
     */
    public class HashTable {
    /**
    * 哈希表的底层是数组
    */
    Student[] hashArray;
    
    
    /**
    * 初始化数组的大小
    */
    int arraySize = 101;
    
    
    /**
    * 设定初始化哈希表的大小 无参构造函数
    */
    public HashTable() {
    hashArray = new Student[arraySize];
    }
    
    
    /**
    * 指定哈希表的大小 有参构造函数
    */
    public HashTable(int arraySize) {
    this.arraySize = arraySize;
    hashArray = new Student[arraySize];
    }
    
    
    /**
    * 获取哈希值
    * 
    * @param key
    * @return
    */
    public int hashCode(String key) {
    int hashVal = 0;
    int power10 = 1;
    for (int i = key.length() - 1; i >= 0; i--) {
    hashVal = hashVal + (key.charAt(i) - 48) * power10; // 10的幂的连乘
    power10 = power10 * 10;
    }
    return hashVal % hashArray.length; // 取模
    }
    
    
    /**
    * 添加数据
    * 
    * @param student
    */
    public void add(Student student) {
    int hashVal = hashCode(student.getKey()); // student若为空,则报空指针异常
    for (int i = 0; i < arraySize; i++) {
    if (hashArray[hashVal] == null) {
    hashArray[hashVal] = student;
    return;
    }
    hashVal++; // 寻找下一个空白位置
    hashVal %= hashArray.length; // 取摸,避免数组越界
    }
    }
    
    
    /**
    * 删除数据并返回
    * 
    * @param student
    * @return
    */
    public Student delete(Student student) {
    int hashVal = hashCode(student.getKey()); // student若为空,则报空指针异常
    for (int i = 0; i < arraySize; i++) {
    if (hashArray[hashVal] == student) {
    hashArray[hashVal] = null;
    return student;
    }
    hashVal++; // 寻找下一个空白位置
    hashVal %= hashArray.length; // 取摸,避免数组越界
    }
    return null; // 不存在该信息
    }
    
    
    /**
    * 查找并返回
    * 
    * @param student
    * @return
    */
    public Student find(Student student) {
    int hashVal = hashCode(student.getKey()); // student若为空,则报空指针异常
    for (int i = 0; i < arraySize; i++) {
    if (hashArray[hashVal] == student) {
    return hashArray[hashVal];
    }
    hashVal++; // 寻找下一个空白位置
    hashVal %= hashArray.length; // 取摸,避免数组越界
    }
    return null; // 不存在该信息
    }
    
    
    /**
    * 显示数据
    */
    public void display() {
    StringBuilder str = new StringBuilder(); // 字符串拼接
    str.append("[");
    for (int i = 0; i < arraySize; i++) {
    if (hashArray[i] != null) {
    str.append(hashArray[i].getKey() + ", ");
    }
    }
    str.replace(str.length() - 2, str.length() - 1, "]"); // 不包含起始值
    System.out.println(str.toString());
    
    
    }
    
    
    /**
    * 测试
    * 
    * @param args
    */
    public static void main(String[] args) {
    HashTable hashTable = new HashTable();
    
    
    // 添加
    Student s1 = new Student("1");
    Student s2 = new Student("2");
    Student s3 = new Student("3");
    Student s4 = new Student("4");
    Student s5 = new Student("5");
    Student s6 = new Student("2");
    hashTable.add(s1);
    hashTable.add(s2);
    hashTable.add(s3);
    hashTable.add(s4);
    hashTable.add(s5);
    hashTable.add(s6);
    
    
    // 显示
    System.out.println("显示全部元素:");
    hashTable.display();
    
    
    // 删除
    System.out.println("删除对象s6后,剩余元素为:");
    hashTable.delete(s6);
    hashTable.display();
    
    // 查找
    if(hashTable.find(s6) == null)
    System.out.println("不存在s6该信息");
    
    }
    }
    


    3.2.3 测试结果

     






    3.3二次探测法

    3.3.1 原理

    如果哈希函数计算的原始下班为1000,线性探测查找空白就是1001,1002,1003,依此类推。而在二次探测法中,探测的过程是1000+12, 1000+22, 1000+32, 等等。即使跨度变大,依然会产生聚集,称为二次聚集。由于代码和线性探测类似,这里不再演示。


    3.4 再哈希法

    3.4.1 原理

    再哈希法使用一种依赖关键字的探测序列,消除原始聚集和二次聚集等问题。核心步骤是将关键字再做一次哈希化,用这个结果作为步长,从而保证不同关键字探测序列不同。


    3.4.2 完整代码

    public class HashTable {
    /**
    * 哈希表的底层是数组
    */
    Student[] hashArray;
    
    
    /**
    * 初始化数组的大小
    */
    int arraySize = 101;
    
    
    
    
    /**
    * 设定初始化哈希表的大小 无参构造函数
    */
    public HashTable() {
    hashArray = new Student[arraySize];
    }
    
    
    /**
    * 指定哈希表的大小 有参构造函数
    */
    public HashTable(int arraySize) {
    this.arraySize = arraySize;
    hashArray = new Student[arraySize];
    }
    
    
    /**
    * 第1个哈希函数
    * 用于找到原始位置
    * @param key
    * @return
    */
    public int hashCode(String key) {
    int hashVal = 0;
    int power10 = 1;
    for (int i = key.length() - 1; i >= 0; i--) {
    hashVal = hashVal + (key.charAt(i) - 48) * power10; // 10的幂的连乘
    power10 = power10 * 10;
    }
    return hashVal % hashArray.length; // 取模
    }
    
    
    /**
    * 第2个哈希函数
    * 生成步长
    * @param key
    * @return
    */
    public int hashFun(String key){
    int hashVal = 0;
    int power10 = 1;
    for (int i = key.length() - 1; i >= 0; i--) {
    hashVal = hashVal + (key.charAt(i) - 48) * power10; // 10的幂的连乘
    power10 = power10 * 10;
    }
    return 5 - (hashVal % 5); // 1)和第一1哈希函数不同 2)不能输出为0 
    }
    /**
    * 添加数据
    * 
    * @param student
    */
    public void add(Student student) {
    int hashVal = hashCode(student.getKey()); // student若为空,则报空指针异常
    // 步长stepSize = constant - (key % constant)
    //  constant是小于数组容量的质数,如5,3等
    int setpSize = hashFun(student.getKey()); 
    for (int i = 0; i < arraySize; i++) {
    if (hashArray[hashVal] == null) {
    hashArray[hashVal] = student;
    return;
    }
    hashVal += setpSize; // 寻找下一个空白位置
    hashVal %= arraySize; // 取摸,避免数组越界
    }
    }
    
    
    /**
    * 删除数据并返回
    * 
    * @param student
    * @return
    */
    public Student delete(Student student) {
    int hashVal = hashCode(student.getKey()); // student若为空,则报空指针异常
    int setpSize = hashFun(student.getKey()); // 步长
    for (int i = 0; i < arraySize; i++) {
    if (hashArray[hashVal] == student) {
    hashArray[hashVal] = null;
    return student;
    }
    hashVal += setpSize; // 寻找下一个空白位置
    hashVal %= arraySize; // 取摸,避免数组越界
    }
    return null; // 不存在该信息
    }
    
    
    /**
    * 查找并返回
    * 
    * @param student
    * @return
    */
    public Student find(Student student) {
    int hashVal = hashCode(student.getKey()); // student若为空,则报空指针异常
    int setpSize = hashFun(student.getKey()); // 步长
    for (int i = 0; i < arraySize; i++) {
    if (hashArray[hashVal] == student) {
    return hashArray[hashVal];
    }
    hashVal += setpSize; // 寻找下一个空白位置
    hashVal %= arraySize; // 取摸,避免数组越界
    }
    return null; // 不存在该信息
    }
    
    
    /**
    * 显示数据
    */
    public void display() {
    StringBuilder str = new StringBuilder(); // 字符串拼接
    str.append("[");
    for (int i = 0; i < arraySize; i++) {
    if (hashArray[i] != null) {
    str.append(hashArray[i].getKey() + ", ");
    }
    }
    str.replace(str.length() - 2, str.length() - 1, "]"); // 不包含起始值
    System.out.println(str.toString());
    }
    
    
    /**
    * 测试
    * 
    * @param args
    */
    public static void main(String[] args) {
    HashTable hashTable = new HashTable();
    
    
    // 添加
    Student s1 = new Student("1");
    Student s2 = new Student("2");
    Student s3 = new Student("3");
    Student s4 = new Student("4");
    Student s5 = new Student("5");
    Student s6 = new Student("2");
    hashTable.add(s1);
    hashTable.add(s2);
    hashTable.add(s3);
    hashTable.add(s4);
    hashTable.add(s5);
    hashTable.add(s6);
    
    // 显示
    System.out.println("显示全部元素:");
    hashTable.display();
    
    
    // 删除
    System.out.println("删除对象s6后,剩余元素为:");
    hashTable.delete(s6);
    hashTable.display();
    
    // 查找
    if(hashTable.find(s6) == null)
    System.out.println("不存在s6信息");
    
    
    }
    }
    
    

    3.4.3 测试结果









    4 链地址法

    4.1 原理

    在哈希表每个单元中设置链表。某个数据项的关键字还是像通常一样映射到哈希表的单元中,而数据项本身插入到单元的链表中。


    4.2 完整代码

    public class Node { 
    // 数据域
    public Student student; 
    // 上一个节点
    public Node previous; 
    /**
    * 有参构造函数
    */
    public Node(Student student) {
    super();
    this.student = student;
    } 
    /**
    * 显示当前节点
    */
    public void showCurrentNode(){
    System.out.println("stuNo is " + student.getKey());
    }
    } 
    public class Link { 
    /**
    * 尾结点
    */
    private Node last; 
    /**
    * 无参构造函数
    */
    public Link() {
    last = null;
    } 
    /**
    * 在尾部插入节点
    * @param student
    */
    public void insertLast(Student student) {
    Node node = new Node(student);
    node.previous = last;
    last = node;
    }; 
    /**
    * 查找
    * @param student
    * @return
    */
    public Student find(Student student) {
    Node current = last; // 临时变量
    while (current != null) { // 循环查找
    if (current.student == student) {
    return student;
    }
    current = current.previous;
    }
    System.out.println("该学生不存在!");
    return null;
    } 
    /**
    * 删除最后一个节点并返回
    * @return
    */
    public Node deleteLast() {
    Node current = last;
    last = last.previous;
    return current;
    } 
    /**
    * 删除节点并返回
    * @param student
    * @return
    */
    public Student delete(Student student) {
    if(last != null && last.student == student){ //判断是否尾节点
    last = last.previous;
    return student;
    } else{ //非尾节点
    Node current = last.previous;//表示当前节点
    Node currentNext = last; //表示当前节点的下一个节点
    while (current != null) {
    if (current.student == student) {
    currentNext.previous = current.previous; //删除当前节点
    return current.student;
    }
    currentNext = current;
    current = current.previous;
    }
    }
    System.out.println("所要删除的节点不存在!");
    return null;
    } 
    /**
    * 显示所有节点信息
    */
    public void display() {
    Node current = last;
    while (current != null) {
    current.showCurrentNode();
    current = current.previous;
    }
    // 换行
    System.out.println();
    }
    } 
    public class HashTable {
    /**
    * 哈希表的底层是数组
    */
    Link[] hashArray; 
    /**
    * 设定初始化哈希表的大小 无参构造函数
    */
    public HashTable() {
    hashArray = new Link[101];
    } 
    /**
    * 指定哈希表的大小 有参构造函数
    */
    public HashTable(int arraySize) {
    hashArray = new Link[arraySize];
    } 
    /**
    * 获取哈希值
    * 
    * @param key
    * @return
    */
    public int hashCode(String key) {
    int hashVal = 0;
    int power10 = 1;
    for (int i = key.length() - 1; i >= 0; i--) {
    hashVal = hashVal + (key.charAt(i) - 48) * power10; // 10的幂的连乘
    power10 = power10 * 10;
    }
    return hashVal % hashArray.length; // 取模
    } 
    /**
    * 添加数据
    * 
    * @param student
    */
    public void add(Student student) {
    int hashVal = hashCode(student.getKey()); // student若为空,则报空指针异常
    if (hashArray[hashVal] == null) { // 判断是否为空
    hashArray[hashVal] = new Link(); // 将链表添加到哈希表中
    }
    hashArray[hashVal].insertLast(student); // 在链表尾部插入数据
    } 
    /**
    * 删除数据并返回
    * 
    * @param student
    * @return
    */
    public Student delete(Student student) {
    int hashVal = hashCode(student.getKey()); // student若为空,则报空指针异常
    return hashArray[hashVal].delete(student);
    } 
    /**
    * 查找并返回
    * 
    * @param student
    * @return
    */
    public Student find(Student student) {
    int hashVal = hashCode(student.getKey()); // student若为空,则报空指针异常
    if (hashArray[hashVal].find(student) != null) {
    return hashArray[hashVal].find(student);
    }
    return null;
    } 
    /**
    * 显示数据
    */
    public void display() {
    for (int i = 0; i < hashArray.length; i++) {
    if (hashArray[i] != null) {
    hashArray[i].display();
    }
    }
    } 
    /**
    * 测试
    * 
    * @param args
    */
    public static void main(String[] args) {
    HashTable hashTable = new HashTable(); 
    // 添加
    Student s1 = new Student("1");
    Student s2 = new Student("2");
    Student s3 = new Student("3");
    Student s4 = new Student("4");
    Student s5 = new Student("5");
    hashTable.add(s1);
    hashTable.add(s2);
    hashTable.add(s2);
    hashTable.add(s3);
    hashTable.add(s4);
    hashTable.add(s5); 
    // 显示
    System.out.println("显示全部元素:");
    hashTable.display(); 
    //删除
    System.out.println("删除对象s2后,剩余元素为:");
    hashTable.delete(s2);
    hashTable.display();
    } 
    }
    


    4.3 测试结果

     


    5 开放地址法和链地址法的对比

    在开发地址法中,当装填因子(插入元素和哈希表底层数组大小的比值)超过1/2或2/3后,性能下降得很快。在链地址发中填充因子即使达到1以上,对性能都影响不大。因此,链地址法是更健壮的机制,特别是哈希表的存储容量不清楚的前提下。


    6 参考文献

    [1] Robert, Lafore., Java数据结构和算法.第2版 版. 2004: 中国电力出版社.
    [2] Sedgewick Robert与Wayne  Kevin, 算法. 2012: 人民邮电出版社.


    展开全文
  • 了解一致性哈希算法

    2019-10-09 01:12:03
    一致性哈希算法是为了解决普通哈希算法的热点问题,当使用普通哈希算法来切割数据到不同的缓存服务器时。 一旦缓存服务器的数量产生变化,客户端向缓存服务器请求相应的数据就不会命中,转而请求具体的数据库服务器...

    用途

    一致性哈希算法是为了解决普通哈希算法的热点问题,当使用普通哈希算法来切割数据到不同的缓存服务器时。
    一旦缓存服务器的数量产生变化,客户端向缓存服务器请求相应的数据就不会命中,转而请求具体的数据库服务器,从而造成 缓存击穿

    下面我们来看一下使用普通哈希算法时所带来的问题,假如我们拥有 10 台缓存服务器,那么我们在存放数据的时候可以对缓存数据项的 Key 进行哈希操作,取得其散列值,并将其与服务器数量进行取模运算,就可以得到一个服务器下标的数字。

    服务器信息 = Hash(Key) % 10

    例如我针对字符串 "140" 进行 SHA256 散列操作,得到 762818267,对 10 取模运算结果是 7 号服务器。但如果增加了一台服务器,那么就会变成对 11 取模,,其结果就是 2 号服务器,得到的位置完全不正确,造成取缓存的时候肯定不会命中。

    原理

    注意:

    由于画图的时候粗心将服务器 C 的 IP 地址写成了 192.168.100.102,其真实 IP 应该是 192.168.100.103,阅读文章的时候请注意这个区别。

    1.创建一个环,这个哈希环有 2^32 个节点。

    1203160-20190326172611637-1159995295.png

    2.求出服务器的哈希值,并将其与哈希环节点的数量取模,得到的值即是服务器节点在哈希环上的位置。

    1203160-20190326172625771-1764123293.png

    3.根据要存储的数据项键值,求出其哈希值,与哈希环节点数量取模,得到在哈希环的位置。

    1203160-20190326172638613-1036473557.png

    4.根据数据项在哈希环的位置,顺时针查找遇到的第一个服务器节点,将数据项存放到该服务器。

    1203160-20190326172650517-318650619.png

    5.如果增加了一台服务器 D,只会影响 D 之前区间的数据。

    1203160-20190326172704176-795099344.png

    上述情况仅适用于服务节点在哈希环上分布均匀的情况,如果哈希环上服务器节点的 分布位置不均匀,则会导致某个区间内的数据项的大量数据存放在一个服务器节点中。如下图,A 缓存服务器就会接收大量请求,当该服务器崩溃掉之后,B 服务器,C 服务器会依次崩溃,这样就会造成 服务器雪崩效应,整个缓存服务器集群都会瘫痪。

    1203160-20190326172719135-296124833.png

    这种时候,我们可以引入虚拟节点来解决该问题。例如我们拥有 A、B、C 三台服务器,我们在哈希环上创建哈希服务器的时候,可以为其创建 N 个虚拟节点,这些虚拟节点都是指向真实服务器的 IP,这样我们在哈希环上的服务器节点分布就会很均匀。

    1203160-20190326172731752-1780650091.png

    实现

    在这里我们基于 C# 与 .NET Core 编写一个 DEMO 代码,用来演示上述情况,这里的代码仅作演示使用,如果要应用到生产环境,请注意线程同步问题。

    using System;
    using System.Collections.Generic;
    using System.Security.Cryptography;
    using System.Text;
    
    /*
     * 一致性哈希算法的 DEMO,主要用于演示一致性哈希算法的实现与实际应用。
     */
    
    namespace ConsistentHashing.Startup
    {
        public class NodeInfo
        {
            public string IPAddress { get; set; }
        }
    
        public class VirtualNodeInfo
        {
            public string NodeName { get; set; }
    
            public NodeInfo RealNodeInfo { get; set; }
        }
    
        public class ConsistentHashing
        {
            // 哈希环的大小
            private readonly int _ringCount;
            // 每个物理节点对应的虚拟节点数量
            private readonly int _virtualNodeCount;
    
            // 哈希环
            public readonly VirtualNodeInfo[] HashRing;
    
            public ConsistentHashing(int ringCount = int.MaxValue, int virtualNodeCount = 3)
            {
                _ringCount = ringCount;
                _virtualNodeCount = virtualNodeCount;
                HashRing = new VirtualNodeInfo[_ringCount];
            }
    
            public NodeInfo GetNode(string key)
            {
                var pos = Math.Abs(GetStandardHashCode(key) % _ringCount);
                // 顺时针查找最近的节点
                return GetFirstNodeInfo(pos).RealNodeInfo;
            }
    
            /// <summary>
            /// 向哈希环上添加虚拟节点。
            /// </summary>
            public void AddNode(NodeInfo info)
            {
                for (int index = 0; index < _virtualNodeCount; index++)
                {
                    // 哈希环上没有物理节点,只有虚拟节点
                    var virtualNodeName = $"{info.IPAddress}#{index}";
                    var hashIndex = Math.Abs(GetStandardHashCode(virtualNodeName) % _ringCount);
                    
                    // 搜索空的哈希环位置
                    var emptyIndex = GetEmptyNodeIndex(hashIndex);
    
                    if (emptyIndex == -1)
                    {
                        break;
                    }
                    
                    HashRing[emptyIndex] = new VirtualNodeInfo{NodeName = virtualNodeName,RealNodeInfo = info};
                }
            }
    
            public void RemoveNode(NodeInfo info)
            {
                // 构建虚拟节点的 KEY
                var virtualNames = new List<string>();
                for (int i = 0; i < _virtualNodeCount; i++)
                {
                    virtualNames.Add($"{info.IPAddress}#{i}");
                }
    
                for (int i = 0; i < HashRing.Length; i++)
                {
                    if(HashRing[i] == null) continue;
                    if (virtualNames.Contains(HashRing[i].NodeName)) HashRing[i] = null;
                }
            }
    
            /// <summary>
            /// 计算指定 KEY 的 HASH 值
            /// </summary>
            private int GetStandardHashCode(string key)
            {
                var sha1 = SHA256.Create();
                var hashValue = sha1.ComputeHash(Encoding.UTF8.GetBytes(key));
                return BitConverter.ToInt32(hashValue);
            }
    
            /// <summary>
            /// 循环遍历哈希环,寻找空节点的索引,防止覆盖存在的节点信息。
            /// </summary>
            private int GetEmptyNodeIndex(int startFindIndex)
            {
                while (true)
                {
                    if (HashRing[startFindIndex] == null)
                    {
                        return startFindIndex;
                    }
    
                    var nextIndex = GetNextNodeIndex(startFindIndex);
                    // 说明已经遍历了整个哈希环,说明没有空的节点了。
                    if (startFindIndex == nextIndex)
                    {
                        return -1;
                    }
    
                    startFindIndex = nextIndex;
                }
            }
    
            /// <summary>
            /// 根据指定的索引,获得哈希环的下一个索引。这里需要注意的是,因为哈希环是一个环形,当
            /// 当前位置为环的末尾时,应该从 0 开始查找。
            /// </summary>
            private int GetNextNodeIndex(int preIndex)
            {
                if (preIndex == HashRing.Length - 1) return 0;
    
                return ++preIndex;
            }
    
            private VirtualNodeInfo GetFirstNodeInfo(int currentIndex)
            {
                VirtualNodeInfo nodeInfo = null;
                int nextIndex = currentIndex;
                while (nodeInfo == null)
                {
                    nodeInfo = HashRing[GetNextNodeIndex(nextIndex)];
                    nextIndex += 1;
                }
                
                return nodeInfo;
            }
        }
    
        internal class Program
        {
            private static void Main(string[] args)
            {
                var consistentHashing = new ConsistentHashing(400,10);
                consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.101"});
                consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.102"});
                consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.103"});
                consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.104"});
    
                foreach (var node in consistentHashing.HashRing)
                {
                    Console.WriteLine(node?.NodeName ?? "NULL");
                }
    
                // 存放 Id 为 15 的缓存服务器
                var nodeInfo = consistentHashing.GetNode("15");
                
                // 删除节点测试
                consistentHashing.RemoveNode(new NodeInfo {IPAddress = "192.168.1.103"});
            }
        }
    }

    转载于:https://www.cnblogs.com/myzony/p/10601554.html

    展开全文
  • 哈希算法说明及示例

    2020-10-30 16:24:37
    定义:哈希算法又叫散列算法,是将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。它的原理其实很简单,就是把一段交易信息转换成一个固定长度的字符串 特点: 1. 信息相同,...
  • FNV哈希算法

    2016-03-22 20:36:00
    由来:FNV哈希算法全名为Fowler-Noll-Vo算法,是以三位发明人Glenn Fowler,Landon Curt Noll,Phong Vo的名字来命名的,最早在1991年提出。 特点和用途:FNV能快速hash大量数据并保持较小的冲突率,它的高度分散使...
  • 什么是哈希算法

    千次阅读 2018-05-07 18:27:19
    哈希函数,又称哈希算法,它通过一个函数,把任意长度的数据转换为一个长度固定的数据串(通常用16进制的字符串表示)。 Hash算法特别的地方在于它是一种单向算法,用户可以通过Hash算法对目标信息生成一段特定长度...
  • 感知哈希算法

    2014-08-29 16:35:00
    ”感知哈希算法”(Perceptual hash algorithm),它的作用是对每张图片生成一个”指纹”(fingerprint)字符串,然后比较不同图片的指纹。结果越接近,就说明图片越相似。 优点:简单快速,不受图片大小缩放的影响...
  • 1、一致性哈希算法及其用途 假设现在有一批数据需要均匀地分布在若干台服务器上,这批数据满足以下假定: 所有数据的访问频率一致。 数据的访问都是随机的。 不管数据规模多大,都希望数据的分布是均匀的 不断...
  • FNV哈希算法【转】

    2017-11-23 13:22:00
    转自:... 由来:FNV哈希算法全名为Fowler-Noll-Vo算法,是以三位发明人Glenn Fowler,Landon Curt Noll,Phong Vo的名字来命名的,最早在1991年提出。 特点和用途:FNV能快速hash大量数据并保持...
  • 1、Hash 算法分类 MD5 和 SHA-1 是目前应用最广泛的 Hash 算法且是以 MD4 算法为基础设计的。 1) MD4 MD4(RFC 1320) 是 MIT 的 Ronald L. Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写。 它适用在 32 ...
  • 由来:FNV哈希算法全名为Fowler-Noll-Vo算法,是以三位发明人Glenn Fowler,Landon Curt Noll,Phong Vo的名字来命名的,最早在1991年提出。特点和用途:FNV能快速hash大量数据并保持较小的冲突率,它的高度分散使它...
  • 我在电信行业和信息安全行业里的工作经历发现,目前网络上的哈希算法都在查询速度上远远无法满足日趋增长的网络大数据要求。因此产生了自己写算法的想法。 现在我把自己的算法初稿发布出来,用我在一家信息安全的...
  • 一、hash算法 著名的hash算法,MD5和SHA1...哈希算法有如下特性: 1)不可以从消息摘要中复原信息; 2)两个不同的消息不会产生同样的消息摘要; 1.1 MD5算法 MD5是RSA数据安全
  • 由来:FNV哈希算法全名为Fowler-Noll-Vo算法,是以三位发明人Glenn Fowler,Landon Curt Noll,Phong Vo的名字来命名的,最早在1991年提出。特点和用途:FNV能快速hash大量数据并保持较小的冲突率,它的高度分散使它...
  • 转载自公众号:图解...首先我们思考一下 AHI 是为了解决什么问题:随着 MySQL 单表数据量增大,(尽管 B+ 树算法极好地控制了树的层数)索引 B+ 树的层数会逐渐增多;随着索引树层数增多,检索某一个数据页...
  • 哈希函数之MD5算法

    2021-01-02 04:17:02
    算法全称为: ...2004年被证明MD5无法防止碰撞攻击,因此不适用于安全认证,比如SSL公开密钥认证或者数字签名等用途。2011年,RFC 6151 禁止MD5用作密钥散列消息认证码。 现在一般用SHA-2. 参考维基百科 ...
  • 哈希哈希

    2019-09-28 18:47:25
    哈希算法是通过一个哈希函数 H,将一种数据(字符串、大数等)转化为能够用变量表示或者能直接作为数组下标的数,通过哈希函数转化得到的数值我们成为哈希值。通过哈希值可以实现快速查找和匹配。本文主要介绍两种...
  • 一步一步写算法(之哈希二叉树) 原文: 一步一步写算法(之哈希二叉树) 【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 用过平衡二叉树的朋友都...
  • java数据结构和算法(哈希表)

    千次阅读 2016-10-02 11:51:06
    什么是哈希表? 哈希表是一种数据结构,提供快速的插入和查找操作。 优点: 插入、查找、删除的时间级为O(1);...数据项占哈希表长的一半,或者三分之二时,哈希表的性能最好...用途: 不需要遍历数据并且可以提前预
  • 哈希表:hash(杂乱信息的意思) 的音译,用来把一些杂乱无章的信息根据其关键字的特点映射到一个连续的空间,操作简单,用途广泛,例如:电子词典。 这里用到的映射方法称为 索引方法。对应的实现函数称为哈希函数。...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 195
精华内容 78
关键字:

哈希算法用途