精华内容
下载资源
问答
  • 1 哈希表复杂度分析(链地址法) 一共有 M 个地址,如果放入的总元素个数是 N 如果每个地址是链表,O(N / M) 如果每个地址是平衡树:O(log( N / M)) 2 哈希表的动态空间处理 当平均每个地址承载的元素超过一定...

    1 哈希表复杂度分析(链地址法

    一共有 M 个地址,如果放入的总元素个数是 N

    • 如果每个地址是链表,O(N / M)
    • 如果每个地址是平衡树:O(log( N / M))
      在这里插入图片描述

    2 哈希表的动态空间处理

    • 当平均每个地址承载的元素超过一定程度,即扩容,N / M >= upperTol
    • 当平均每个地址承载的元素少过一定程度,即缩容, N / M < lowerTol
    • HashTable.java
    package hashtable;
    
    import java.util.TreeMap;
    
    public class HashTable<K, V> {
    
        private static final int upperTol = 10;
        private static final int lowerTol = 2;
        private static final int initCapacity = 7;
    
        private TreeMap<K, V>[] hashtable;
        private int M;
        private int size;
    
        public HashTable(int M) {
            this.M = M;
            size = 0;
            hashtable = new TreeMap[M];
    
            for (int i = 0; i < M; i++) {
                hashtable[i] = new TreeMap<>();
            }
        }
    
        public HashTable() {
            this(initCapacity);
        }
    
        private int hash(K key) {
            // 负数可以变成正数
            return (key.hashCode() & 0x7fffffff) % M;
        }
    
        public int getSize() {
            return size;
        }
    
        public void add(K key, V value) {
    
            TreeMap<K, V> map = hashtable[hash(key)];
    
            if (map.containsKey(key)) {
                map.put(key, value);
            } else {
                map.put(key, value);
                size++;
    
                if (size >= upperTol * M) {
                    resize(2 * M);
                }
            }
        }
    
        public V remove(K key) {
            TreeMap<K, V> map = hashtable[hash(key)];
            V ret = null;
            if (map.containsKey(key)) {
                ret = map.remove(key);
                size--;
    
                if (size < lowerTol * M && M / 2 >= initCapacity) {
                    resize(M / 2);
                }
    
            }
    
            return ret;
        }
    
        public void set(K key, V value) {
            TreeMap<K, V> map = hashtable[hash(key)];
    
            if (!map.containsKey(key)) {
                throw new IllegalArgumentException(key + "not exist");
            }
    
            map.put(key, value);
        }
    
        public boolean contains(K key) {
            return hashtable[hash(key)].containsKey(key);
        }
    
        public V get(K key) {
            return hashtable[hash(key)].get(key);
        }
    
        private void resize(int newM) {
    
            TreeMap<K, V>[] newHashTable = new TreeMap[newM];
    
            for (int i = 0; i < newM; i++) {
                newHashTable[i] = new TreeMap<>();
            }
    
            int oldM = M;
            this.M = newM;
            for (int i = 0; i < oldM; i++) {
    
                TreeMap<K, V> map = hashtable[i];
    
                for (K key : map.keySet()) {
                    newHashTable[hash(key)].put(key, map.get(key));
                }
            }
    
            this.hashtable = newHashTable;
        }
    
    
    }
    
    

    3 更复杂的动态空间处理

    • 2 * M 不是素数
    • 解决方式:按照下表扩容
      在这里插入图片描述
    • HashTable.java
    package hashtable;
    
    import java.util.TreeMap;
    
    public class HashTable<K, V> {
    
    
        private final int[] capacity = {
                53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
                49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
                12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
                805306457, 1610612741};
    
        private static final int upperTol = 10;
        private static final int lowerTol = 2;
        private int capacityIndex = 0;
    
        private TreeMap<K, V>[] hashtable;
        private int M;
        private int size;
    
        public HashTable() {
            this.M = capacity[capacityIndex];
            size = 0;
            hashtable = new TreeMap[M];
    
            for (int i = 0; i < M; i++) {
                hashtable[i] = new TreeMap<>();
            }
        }
    
    
        private int hash(K key) {
            // 负数可以变成正数
            return (key.hashCode() & 0x7fffffff) % M;
        }
    
        public int getSize() {
            return size;
        }
    
        public void add(K key, V value) {
    
            TreeMap<K, V> map = hashtable[hash(key)];
    
            if (map.containsKey(key)) {
                map.put(key, value);
            } else {
                map.put(key, value);
                size++;
    
                if (size >= upperTol * M && capacityIndex + 1 < capacity.length) {
                    capacityIndex++;
                    resize(capacity[capacityIndex];
                }
            }
        }
    
        public V remove(K key) {
            TreeMap<K, V> map = hashtable[hash(key)];
            V ret = null;
            if (map.containsKey(key)) {
                ret = map.remove(key);
                size--;
    
                if (size < lowerTol * M && capacityIndex - 1 >= 0) {
                    capacityIndex--;
                    resize(capacity[capacityIndex]);
                }
    
            }
    
            return ret;
        }
    
        public void set(K key, V value) {
            TreeMap<K, V> map = hashtable[hash(key)];
    
            if (!map.containsKey(key)) {
                throw new IllegalArgumentException(key + "not exist");
            }
    
            map.put(key, value);
        }
    
        public boolean contains(K key) {
            return hashtable[hash(key)].containsKey(key);
        }
    
        public V get(K key) {
            return hashtable[hash(key)].get(key);
        }
    
        private void resize(int newM) {
    
            TreeMap<K, V>[] newHashTable = new TreeMap[newM];
    
            for (int i = 0; i < newM; i++) {
                newHashTable[i] = new TreeMap<>();
            }
    
            int oldM = M;
            this.M = newM;
            for (int i = 0; i < oldM; i++) {
    
                TreeMap<K, V> map = hashtable[i];
    
                for (K key : map.keySet()) {
                    newHashTable[hash(key)].put(key, map.get(key));
                }
            }
    
            this.hashtable = newHashTable;
        }
    
    
    }
    
    

    4 哈希表

    • 均摊复杂度为 O(1)
    • 牺牲了 顺序性
      在这里插入图片描述

    5 自定义的哈希表的 bug

    在这里插入图片描述

    5.1 Java8 中的哈希表

    • Java8 之前每一个位置对应一个链表;Java8 开始,当哈希冲突达到一定的程度,每一个位置从链表转成红黑树;
    • 因为初始的是链表,所以不要求 K 是 Comparable;
    • 转成红黑树的条件:K 是 Comparable,否则依然保持链表;
    展开全文
  • 哈希表与时间复杂度

    千次阅读 2020-12-27 17:58:05
    哈希表 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来...哈希表 是使用 O(1)O(1)时间复杂度 进行数据的插入删除和查找,但

    哈希表

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

    哈希表 是使用 O(1)O(1)时间复杂度 进行数据的插入删除和查找,但是哈希表不保证表中数据的有序性,这样在哈希表中查找最大数据或者最小数据的时间是 O(N)O(N) 实现。

    复杂度

    时间复杂度:O(n),其中 n 为字符串的长度。我们只需同时遍历一遍字符串 s和 t 即可。
    空间复杂度:O(∣Σ∣),其中 Σ 是字符串的字符集。哈希表存储字符的空间取决于字符串的字符集大小,最坏情况下每个字符均不相同,需要 O(∣Σ∣) 的空间。

    基本概念

    • 若关键字为k,则其值存放在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。
    • 对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为冲突(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数 f(k)处理冲突 的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
    • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

    常用方法

    散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位。
    实际工作中需视不同的情况采用不同的哈希函数,通常考虑的因素有:

    • 计算哈希函数所需时间

    • 关键字的长度

    • 哈希表的大小

    • 关键字的分布情况

    • 记录的查找频率

      1.直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)。若其中H(key)中已经有值了,就往下一个找,直到H(key)中没有值了,就放进去。

    1. 数字分析法:分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

    2. 平方取中法:当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。
      例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址.

    3. 折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    4. 随机数法:选择一随机函数,取关键字的随机值作为散列地址,即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。

    5. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。 [2]

    展开全文
  • Redis底层详解(一) 哈希表和字典

    万次阅读 多人点赞 2018-06-28 17:27:37
    一文读懂哈希表

    一、哈希表概述

           首先简单介绍几个概念:哈希表(散列表)、映射、冲突、链地址、哈希函数。

           哈希表(Hash table)的初衷是为了将数据映射到数组中的某个位置,这样就能够通过数组下标访问该数据,提高数据的查找速度,这样的查找的平均期望时间复杂度是O(1)的。

           例如四个整数 6、7、9、12 需要映射到数组中,我们可以开一个长度为13(C语言下标从0开始)的数组,然后将对应值放到对应的下标,但是这样做,就会浪费没有被映射到的位置的空间。

           采用哈希表的话,我们可以只申请一个长度为4的数组,如下图所示:

           将每个数的值对数组长度4取模,然后放到对应的数组槽位中,这样就把离散的数据映射到了连续的空间,所以哈希表又称为散列表。这样做,最大限度上提高空间了利用率,并且查找效率还很高。

           那么问题来了,如果这四个数据是6、7、8、11呢?继续看图:

           7 和 11 对4取模的值都是 3,所以占据了同一个槽位,这种情况我们称为冲突 (collision)。一般遇到冲突后,有很多方法解决冲突,包括但不限于 开放地址法、再散列法、链地址法 等等。 Redis采用的是链地址法,所以这里只介绍链地址法,其它的方法如果想了解请自行百度。

          链地址法就是将有冲突的数据用一个链表串联起来,如图所示:

           这样一来,就算有冲突,也可以将有冲突的数据存储在一起了。存储结构需要稍加变化,哈希表的每个元素将变成一个指针,指向数据链表的链表头,每次有新数据来时从链表头插入,可以达到插入的时间复杂度保持O(1)。

            再将问题进行变形,如果4个数据是 "are",  "you",  "OK",  "?" 这样的字符串,如何进行映射呢?没错,我们需要通过一个哈希函数将字符串变成整数,哈希函数的概念会在接下来详细讲述,这里只需要知道它可以把一个值变成另一个值即可,比如哈希函数f(x),调用 f("are") 就可以得到一个整数,f("you") 也可以得到一个整数。

            一个简易的大小写不敏感的字符串哈希函数如下:

    unsigned int hashFunction(const unsigned char *buf, int len) {
        unsigned int hash = (unsigned int)5381;                       // hash初始种子,实验值
        while (len--)
            hash = ((hash << 5) + hash) + (tolower(*buf++));          // hash * 33 + c
        return hash;
    }

            我们看到,哈希函数的作用就是把非数字的对象通过一系列的算法转化成数字(下标),得到的数字可能是哈希表数组无法承载的,所以还需要通过取模才能映射到连续的数组空间中。对于这个取模,我们知道取模的效率相比位运算来说是很低的,那么有没有什么办法可以把取模用位运算来代替呢?

            答案是有!我们只要把哈希表的长度 L 设置为2的幂(L = 2^n),那么 L-1 的二进制表示就是n个1,任何值 x 对 L 取模等同于和 (L-1) 进行位与(C语言中的&)运算。

            介绍完哈希表的基础概念,我们来看看 Redis 中是如何实现字典的。

    二、Redis数据结构定义

         1、哈希表

           哈希表的结构定义在 dict.h/dictht :

    typedef struct dictht {
        dictEntry **table;             // 哈希表数组
        unsigned long size;            // 哈希表数组的大小
        unsigned long sizemask;        // 用于映射位置的掩码,值永远等于(size-1)
        unsigned long used;            // 哈希表已有节点的数量
    } dictht;

           table 是一个数组,数组的每个元素都是一个指向 dict.h/dictEntry 结构的指针;

           size 记录哈希表的大小,即 table 数组的大小,且一定是2的幂;

           used 记录哈希表中已有结点的数量;

           sizemask 用于对哈希过的键进行映射,索引到 table 的下标中,且值永远等于 size-1。具体映射方法很简单,就是对 哈希值 和 sizemask 进行位与操作,由于 size 一定是2的幂,所以 sizemask=size-1,自然它的二进制表示的每一个位(bit)都是1,等同于上文提到的取模;

           如图所示,为一个长度为8的空哈希表。

         2、哈希表节点

           哈希表节点用 dict.h/dictEntry 结构表示,每个 dictEntry 结构存储着一个键值对,且存有一个 next 指针来保持链表结构:

    typedef struct dictEntry {
        void *key;                  // 键
        union {                     // 值
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v;
        struct dictEntry *next;     // 指向下一个哈希表节点,形成单向链表
    } dictEntry;

           key 是键值对中的键;

           是键值对中的值,它是一个联合类型,方便存储各种结构;

           next 是链表指针,指向下一个哈希表节点,他将多个哈希值相同的键值对串联在一起,用于解决键冲突;如图所示,两个dictEntry 的 key 分别是 k0 和 k1,通过某种哈希算法计算出来的哈希值和 sizemask 进行位与运算后都等于 3,所以都被放在了 table 数组的 3号槽中,并且用 next 指针串联起来。

         3、字典

           Redis中字典结构由 dict.h/dict 表示:

    typedef struct dict {
        dictType *type;                        // 和类型相关的处理函数
        void *privdata;                        // 上述类型函数对应的可选参数
        dictht ht[2];                          // 两张哈希表,ht[0]为原生哈希表,ht[1]为 rehash 哈希表
        long rehashidx;                        // 当等于-1时表示没有在 rehash,否则表示 rehash 的下标
        int iterators;                         // 迭代器数量(暂且不谈)
    } dict;

         type 是一个指向 dict.h/dictType 结构的指针,保存了一系列用于操作特定类型键值对的函数;

         privdata 保存了需要传给上述特定函数的可选参数;

         ht 是两个哈希表,一般情况下,只使用ht[0],只有当哈希表的键值对数量超过负载(元素过多)时,才会将键值对迁移到ht[1],这一步迁移被称为 rehash (重哈希),rehash 会在下文进行详细介绍;

         rehashidx 由于哈希表键值对有可能很多很多,所以 rehash 不是瞬间完成的,需要按部就班,那么 rehashidx 就记录了当前 rehash 的进度,当 rehash 完毕后,将 rehashidx 置为-1;

         4、类型处理函数

          类型处理函数全部定义在 dict.h/dictType 中:

    typedef struct dictType {
        unsigned int (*hashFunction)(const void *key);                                         // 计算哈希值的函数
        void *(*keyDup)(void *privdata, const void *key);                                      // 复制键的函数
        void *(*valDup)(void *privdata, const void *obj);                                      // 复制值的函数
        int (*keyCompare)(void *privdata, const void *key1, const void *key2);                 // 比较键的函数
        void (*keyDestructor)(void *privdata, void *key);                                      // 销毁键的函数
        void (*valDestructor)(void *privdata, void *obj);                                      // 销毁值的函数
    } dictType;

           以上的函数和特定类型相关,主要是为了实现多态,看到这个如果懵逼也没关系,下面会一一对其进行介绍。

    三、哈希函数

          类型处理函数中的第一个函数 hashFunction 就是计算某个键的哈希值的函数,对于不同类型的 key,哈希值的计算是不同的,所以在字典进行创建的时候,需要指定哈希函数。

          哈希函数可以简单的理解为就是小学课本上那个函数,即y = f(x),这里的 f(x)就是哈希函数,x是键,y就是哈希值。好的哈希函数应该具备以下两个特质:
           1、可逆性;
           2、雪崩效应:输入值(x)的1位(bit)的变化,能够造成输出值(y)1/2的位(bit)的变化;
           可逆性很容易理解,来看两个图。图(a)中已知哈希值 y 时,键 x 可能有两种情况,所以显然是不可逆的;而图(b)中已知哈希值 y 时,键 x 一定是唯一确定的,所以它是可逆的。从图中看出,函数可逆的好处是:减少冲突。由于 x 和 y 一一对应,所以在没有取模之前,至少是没有冲突的,这样就从本原上减少了冲突。

           雪崩效应是为了让哈希值更加符合随机分布的原则,哈希表中的键分布的越随机,利用率越高,效率也越高。

           Redis源码中提供了一些哈希函数的实现:

          1、整数哈希

    unsigned int dictIntHashFunction(unsigned int key)
    {
        key += ~(key << 15);
        key ^=  (key >> 10);
        key +=  (key << 3);
        key ^=  (key >> 6);
        key += ~(key << 11);
        key ^=  (key >> 16);
        return key;
    }

           2、字符串哈希

    unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
        unsigned int hash = (unsigned int)dict_hash_function_seed;
        while (len--)
            hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
        return hash;
    }

           这些哈希函数是前人经过一系列的实验,科学计算总结得出来的,我们只需要知道有这么些函数就行了。当字典被用作数据库的底层实现, 或者哈希键的底层实现时, Redis 使用 MurmurHash2 算法来计算键的哈希值。MurmurHash 算法最初由 Austin Appleby 于 2008 年发明, 这种算法的优点在于, 即使输入的键是有规律的, 算法仍能给出一个很好的随机分布性, 并且算法的计算速度也非常快。

    四、哈希算法

         1、索引 

           当要将一个新的键值对添加到字典里面或者通过键查找值的时候都需要执行哈希算法,主要是获得一个需要插入或者查找的dictEntry 所在下标的索引,具体算法如下:

           1、通过宏 dictHashKey 计算得到该键对应的哈希值

    #define dictHashKey(d, key) (d)->type->hashFunction(key)

           2、将哈希值和哈希表的 sizemask 属性做位与,得到索引值 index,其中 ht[x] 可以是 ht[0] 或者 ht[1]

    index = dictHashKey(d, key) & d->ht[x].sizemask;

          2、冲突解决

            哈希的冲突一定发生在键值对插入时,插入的  API 是 dict.c/dictAddRaw:

    dictEntry *dictAddRaw(dict *d, void *key)
    {
        int index;
        dictEntry *entry;
        dictht *ht;
        if (dictIsRehashing(d)) _dictRehashStep(d);               // 1、执行rehash
        if ((index = _dictKeyIndex(d, key)) == -1)                // 2、索引定位
            return NULL;
        ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];          // 3、根据是否 rehash ,选择哈希表
        entry = zmalloc(sizeof(*entry));                          // 4、分配内存空间,执行插入
        entry->next = ht->table[index];
        ht->table[index] = entry;
        ht->used++;
        dictSetKey(d, entry, key);                                // 5、设置键
        return entry;
    }

           1、判断当前的字典是否在进行 rehash,如果是,则执行一步 rehash,否则忽略。判断 rehash 的依据就是 rehashidx 是否为 -1;
           2、通过 _dictKeyIndex 找到一个索引,如果返回-1表明字典中已经存在相同的 key,具体参见接下来要讲的 索引定位;
           3、根据是否在 rehash 选择对应的哈希表;
           4、分配哈希表节点 dictEntry 的内存空间,执行插入,插入操作始终在链表头插入,这样可以保证每次的插入操作的时间复杂度一定是 O(1) 的,插入完毕,used属性自增;
           5、dictSetKey 是个宏,调用字典处理函数中的 keyDup 函数进行键的复制;

          3、索引定位

            插入时还需要进行索引定位,以确定节点要插入到哈希表的哪个位置,实现在静态函数 dict.c/_dictKeyIndex 中:

    static int _dictKeyIndex(dict *d, const void *key)
    {
        unsigned int h, idx, table;
        dictEntry *he;
    
        if (_dictExpandIfNeeded(d) == DICT_ERR)                            // 1、rehash 判断
            return -1;
        h = dictHashKey(d, key);                                           // 2、哈希函数计算哈希值
        for (table = 0; table <= 1; table++) {
            idx = h & d->ht[table].sizemask;                               // 3、哈希算法计算索引值
            he = d->ht[table].table[idx];
            while(he) {                          
                if (key==he->key || dictCompareKeys(d, key, he->key))      // 4、查找键是否已经存在
                    return -1;
                he = he->next;
            }
            if (!dictIsRehashing(d)) break;                                // 5、rehash 判断 
        }
        return idx;
    }

           1、判断当前哈希表是否需要进行扩展,具体参见接下来要讲的 rehash;
           2、利用给定的哈希函数计算键的哈希值;
           3、通过位与计算索引,即插入到哈希表的哪个槽位中;

           4、查找当前槽位中的链表里是否已经存在该键,如果存在直接返回 -1;这里的 dictCompareKeys 也是一个宏,用到了keyCompare 这个比较键的函数;
           5、这个判断比较关键,如果当前没有在做 rehash,那么 ht[1] 必然是一个空表,所以不能遍历 ht[1],需要及时跳出循环;

        五、rehash

          千呼万唤始出来,提到了这么多次的 rehash 终于要开讲了。其实没有想象中的那么复杂,随着字典操作的不断执行,哈希表保存的键值对会不断增多(或者减少),为了让哈希表的负载因子维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者太少时,需要对哈希表大小进行扩展或者收缩。

         1、负载因子

           这里提到了一个负载因子,其实就是当前已使用结点数量除上哈希表的大小,即:

    load_factor = ht[0].used / ht[0].size

          2、哈希表扩展

           1、当哈希表的负载因子大于5时,为 ht[1] 分配空间,大小为第一个大于等于 ht[0].used * 2 的 2 的幂;

           2、将保存在 ht[0] 上的键值对 rehash 到 ht[1] 上,rehash 就是重新计算哈希值和索引,并且重新插入到 ht[1] 中,插入一个删除一个;

           3、当 ht[0] 包含的所有键值对全部 rehash 到 ht[1] 上后,释放 ht[0] 的控件, 将 ht[1] 设置为 ht[0],并且在 ht[1] 上新创件一个空的哈希表,为下一次 rehash 做准备;

           Redis 中 实现哈希表扩展调用的是 dict.c/_dictExpandIfNeeded 函数:

    static int _dictExpandIfNeeded(dict *d)
    {
        if (dictIsRehashing(d)) return DICT_OK;
        if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);          // 大小为0需要设置初始哈希表大小为4
        if (d->ht[0].used >= d->ht[0].size &&
            (dict_can_resize ||
             d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))                 // 负载因子超过5,执行 dictExpand
        {
            return dictExpand(d, d->ht[0].used*2);
        }
        return DICT_OK;
    }
    

          3、哈希表收缩

           哈希表的收缩,同样是为 ht[1] 分配空间, 大小等于 max( ht[0].used, DICT_HT_INITIAL_SIZE ),然后和扩展做同样的处理即可。

         六、渐进式rehash

           扩展或者收缩哈希表的时候,需要将 ht[0] 里面所有的键值对 rehash 到 ht[1] 里,当键值对数量非常多的时候,这个操作如果在一帧内完成,大量的计算很可能导致服务器宕机,所以不能一次性完成,需要渐进式的完成。
           渐进式 rehash 的详细步骤如下:
           1、为 ht[1] 分配指定空间,让字典同时持有 ht[0] 和 ht[1] 两个哈希表;
           2、将 rehashidx 设置为0,表示正式开始 rehash,前两步是在 dict.c/dictExpand 中实现的:

    int dictExpand(dict *d, unsigned long size)
    {
        dictht n;
        unsigned long realsize = _dictNextPower(size);                      // 找到比size大的最小的2的幂
        if (dictIsRehashing(d) || d->ht[0].used > size)
            return DICT_ERR;
        if (realsize == d->ht[0].size) return DICT_ERR;
    
        n.size = realsize;                                                 // 给ht[1]分配 realsize 的空间
        n.sizemask = realsize-1;
        n.table = zcalloc(realsize*sizeof(dictEntry*));
        n.used = 0;
        if (d->ht[0].table == NULL) {                                      // 处于初始化阶段
            d->ht[0] = n;
            return DICT_OK;
        }
        d->ht[1] = n;
        d->rehashidx = 0;                                                  // rehashidx 设置为0,开始渐进式 rehash
        return DICT_OK;
    }

           3、在进行 rehash 期间,每次对字典执行 增、删、改、查操作时,程序除了执行指定的操作外,还会将 哈希表 ht[0].table中下标为 rehashidx 位置上的所有的键值对 全部迁移到 ht[1].table 上,完成后 rehashidx 自增。这一步就是 rehash 的关键一步。为了防止 ht[0] 是个稀疏表 (遍历很久遇到的都是NULL),从而导致函数阻塞时间太长,这里引入了一个 “最大空格访问数”,也即代码中的 enmty_visits,初始值为 n*10。当遇到NULL的数量超过这个初始值直接返回。

           这一步实现在 dict.c/dictRehash 中:

    int dictRehash(dict *d, int n) {
        int empty_visits = n*10;
        if (!dictIsRehashing(d)) return 0;
    
        while(n-- && d->ht[0].used != 0) {
            dictEntry *de, *nextde;
    
            assert(d->ht[0].size > (unsigned long)d->rehashidx);
            while(d->ht[0].table[d->rehashidx] == NULL) {
                d->rehashidx++;
                if (--empty_visits == 0) return 1;                                      // 设置一个空访问数量 为 n*10
            }
            de = d->ht[0].table[d->rehashidx];                                          // dictEntry的迁移
            while(de) {
                unsigned int h;
                nextde = de->next;
                h = dictHashKey(d, de->key) & d->ht[1].sizemask;
                de->next = d->ht[1].table[h];
                d->ht[1].table[h] = de;
                d->ht[0].used--;
                d->ht[1].used++;
                de = nextde;
            }
            d->ht[0].table[d->rehashidx] = NULL;
            d->rehashidx++;                                                            // 完成一次 rehash
        }
    
        if (d->ht[0].used == 0) {                                                      // 迁移完毕,rehashdix 置为 -1
            zfree(d->ht[0].table);
            d->ht[0] = d->ht[1];
            _dictReset(&d->ht[1]);
            d->rehashidx = -1;
            return 0;
        }
        return 1;
    }

           4、最后,当 ht[0].used 变为0时,代表所有的键值对都已经从 ht[0] 迁移到 ht[1] 了,释放 ht[0].table, 并且将 ht[0] 设置为 ht[1],rehashidx 标记为 -1 代表 rehash 结束。

         七、字典API

            1、创建字典
            内部分配字典空间,并作为返回值返回,并调用 _dictInit 进行字典的初始化,时间复杂度O(1)。

    dict *dictCreate(dictType *type, void *privDataPtr)

            2、增加键值对
            调用 dictAddRaw 增加一个 dictEntry,然后调用 dictSetVal 设置值,时间复杂度O(1)。

    int dictAdd(dict *d, void *key, void *val)

            3、查找键
            利用哈希算法找到给定键的 dictEntry,时间复杂度O(1)。

    dictEntry *dictFind(dict *d, const void *key)

            4、查找值
            利用 dictFind 找到给定键的 dictEntry,然后获得值,值的类型不确定,所以返回一个万能指针,时间复杂度O(1)。

    void *dictFetchValue(dict *d, const void *key)

            5、删除键

            通过哈希算法找到对应的键,从对应链表移除,时间复杂度O(1)。

    int dictDelete(dict *ht, const void *key)

    展开全文
  • 哈希表的最差复杂度是n2Prerequisite: 先决条件: Hashing data structure 散列数据结构 Problem statement: 问题陈述: Given an array and a sum X, fins any pair which sums to X. Expected time complexity...

    哈希表的最差复杂度是n2

    Prerequisite:

    先决条件:

    Problem statement:

    问题陈述:

    Given an array and a sum X, fins any pair which sums to X. Expected time complexity O(n).

    给定一个数组和一个X ,对求和为X的任何一对进行求和。 预期时间复杂度O(n)

    Example:

    例:

    Input array:
    [4, -1, 6, 5, -2, 2]
    Sum, X=2
    
    Output:
    Pair {4,-2}
    
    Explanation:
    4+(-2)=2 and thus the pair is {4,-2}
    
    

    Solution:

    解:

    Obviously, in brute force, we can solve it by checking each pair sums to X or not. In the worst case, it will take O(n2) which is too costly for the problem. Still, the algorithm would be like the following:

    显然,在蛮力中,我们可以通过检查每对和是否等于X来解决。 在最坏的情况下,将花费O(n 2 ) ,这对于该问题而言过于昂贵。 尽管如此,该算法仍将如下所示:

    For i=0:n-1
        For j=i+1: n-1
            If arr[i]+arr[j]==X
                Return pair {arr[i],arr[j]}
    
    

    To solve this efficiently, we will use hashing. What we need to create is a hash table which will be used as our lookup table. The idea is to lookup whether X-current_element exists in the hash table or not. If we find any element in the hash table, then obviously
    {X-current_element, current_element} is our desired pair.

    为了有效解决此问题,我们将使用哈希。 我们需要创建一个哈希表,该哈希表将用作我们的查找表。 这个想法是要查找哈希表中是否存在X-current_element 。 如果我们在哈希表中找到任何元素,那么显然
    {X-current_element,current_element}是我们想要的对。

    Now, we can create a lookup table by simply inserting each element. Then in another loop, we can start finding whether X-current_element is in the hash table or not. Following is the two-pass algorithm,

    现在,我们只需插入每个元素即可创建查找表。 然后在另一个循环中,我们可以开始查找X-current_element是否在哈希表中。 以下是两次通过算法,

    Create a hash table using set

    使用set创建哈希表

    unordered_set<int> myset;
    //first pass->building the hash table
    For i=0 to n-1
    	current_element=arr[i]
    	Add current_element to look up table, myset if it’s not there 
    End for
    
    

    Find the pair

    找到一对

    //second pass-> finding the pair using the hash table built
    For i=0 to n-1
    	current_element=arr[i]
    	if(X-current_element is in myset)
    		the desired pair is { current_element , X-current_element } 
            and return 
    End for
    
    

    The time complexity of the algorithm is of course O(n) and space complexity is also O(n) for the hash table.

    该算法的时间复杂度当然是O(n),而哈希表的空间复杂度也是O(n)。

    Now, we can further optimize the above algorithm into a single pass.

    现在,我们可以将上述算法进一步优化为一次通过。

    Instead of creating the hash table in a separate pass, we can do both searching and creating in one pass. The idea is if X-current_element is in the hash table then we are done, otherwise, add this current_element to the hash table.

    除了在单独的过程中创建哈希表,我们还可以一次完成搜索和创建过程。 这个想法是,如果X-current_element在哈希表中,那么我们完成了,否则,请将此current_element添加到哈希表中。

    So the algorithm would be:

    因此,算法为:

    //both searching and looking at a time
    For i=0 to n-1
        current_element=arr[i]
        if(X-current_element is in myset)
            the desired pair is { current_element , X-current_element } 
            and return 
        Else
            Add current_element to myset
    End for
    
    

    So, how it guarantees to work?

    那么,它如何保证工作呢?

    We can show that by our example. Where input array is [4, -1, 6, 5, -2, 2]
    If we have used the two-pass algorithm then, we have got {4,-2} as a pair where 4 would be the current_element and-2 would be the X-current_element.

    我们可以通过示例来证明这一点。 输入数组为[4,-1,6,5,-2,2]
    如果我们使用了两次遍历算法,那么我们将{4,-2}作为一对,其中4是current_element ,-2是X-current_element

    But if we use the one-pass algorithm we would get the pair as {-2, 4} where -2 would be the current_element and 4 would be X-current_element.

    但是,如果使用单次通过算法,则该对将为{-2,4},其中-2为current_element,而4为X-current_element

    The reason is when we have 4 as our current_element in our one-pass algorithm then the hash table is empty. Thus we simply add 4.

    原因是当我们在一次通过算法中将4作为current_element时 ,哈希表为空。 因此,我们只需添加4。

    But when we process -2 as our current_element we have X-(-2) to look for which is 2-(-2) and 4 now exists. So the thing is the one pass is guaranteed to work. Only it will return the pair in reverse order.

    但是,当我们将-2作为current_element处理时,我们有X-(-2)来寻找哪个是2-(-2)且现在存在4。 因此,事情是一站式保证有效。 只有它会以相反的顺序返回该对。

    The time & space complexity of the one-pass algorithm is of course same as the two-pass algorithm since it's big O notation.

    一遍算法的时间和空间复杂度当然与二遍算法相同,因为它的O表示法很大。

    C++ implementation:

    C ++实现:

    #include <bits/stdc++.h>
    using namespace std;
    
    pair<int, int> find_pair_sum(vector<int> arr, int n, int X)
    {
        unordered_set<int> myset;
    
        for (int i = 0; i < n; i++) {
            //pair exists current_element, X-current_element
            if (myset.find(X - arr[i]) != myset.end()) {
                return make_pair(arr[i], X - arr[i]);
            }
            //if arr[i] already not there
            else if (myset.find(arr[i]) == myset.end()) 
                myset.insert(arr[i]);
        }
    
        return make_pair(INT_MAX, INT_MAX);
    }
    
    int main()
    {
        cout << "Enter number of input elements,n\n";
        int n;
        cin >> n;
     
        cout << "Enter the input elements\n";
        vector<int> arr(n);
     
        for (int i = 0; i < n; i++)
            cin >> arr[i];
    
        cout << "Enter sum, X\n";
        int X;
        cin >> X;
    
        pair<int, int> p = find_pair_sum(arr, n, X);
        if (p.first == INT_MAX && p.second == INT_MAX)
            cout << "No pairs found\n";
        else
            cout << "The pairs are : " << p.first << ", " << p.second << endl;
    
        return 0;
    }
    
    

    Output:

    输出:

    Enter number of input elements,n
    6
    Enter the input elements
    4 -1 6 5 2 -2
    Enter sum, X
    2
    The pairs are : -2, 4
    
    
    

    翻译自: https://www.includehelp.com/data-structure-tutorial/given-an-array-a-and-number-x-check-for-pair-in-a-with-sum-x-set-1.aspx

    哈希表的最差复杂度是n2

    展开全文
  • 如果采用链地址法来存储元素的话,如果哈希表有M个地址,如果要想放入哈希表的元素为N。 问题: 那么此时每个地址就能存储M/N个元素。此时它们的哈希值是冲突的。 如果每个地址都存储的是链表:O(N/M) 如果...
  • 哈希表中查找一个key的时间复杂度到底是多少?–leetcode 1 不出意外的话,这应该是我的第一篇博客。 今天下午上课,听的东西完全不进脑子,状态奇差(不过好像很多课我都这样),于是打开几个月没碰的...
  • 哈希表

    2021-01-02 15:25:15
    哈希表的时间复杂度O(1) 哈希表的样式 数组就是哈希表 下标就是哈希表的索引 数组元素就是哈希表的数字 哈希函数 通过hashCode把名字转化为数值,hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,...
  • 哈希表(一)——哈希表的大小

    万次阅读 多人点赞 2018-08-30 13:47:27
    哈希表的设计主要是为了查找,为了对内存中的数据进行快速查找,它的查找时间复杂度是O(1)。设计一个哈希表的关键有三个:怎么控制哈希表的长度,怎么设计哈希函数,怎么处理哈希冲突 今天这篇文章先来讨论一下...
  • 一、哈希表1、概念 哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数...
  • 哈希表解法空间复杂度是o(n),用摩尔投票法,空间复杂度是o(1), 摩尔投票法是两个两个的碰撞,进行厮杀。 https://www.bilibili.com/video/BV1it411V784?from=search&seid=3388060042056238482
  • Redis哈希表与jdk哈希表比较Redis哈希表// 字典 typedef struct dict { // 类型 dictType *type; // 私有数据 void *privdata; // 哈希表 // 两个表,一个是使用的表,一个是供rehash使用的表 dictht ht[2]; ...
  • 哈希表 01 哈希表基础

    2019-02-24 15:35:00
    哈希表 哈希函数:将“键”转换为“索引”,键可能是字符串,浮点数,日期等;... 哈希表充分体现了算法设计领域的经典思想:空间换时间; 如果我们有1的空间,我们只能用O(n)的时间复杂度完成各项操作(线性表...
  • 哈希表(散列表)原理详解

    万次阅读 多人点赞 2018-07-03 19:40:58
    什么是哈希表哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数...
  • 数据结构:哈希表

    千次阅读 多人点赞 2021-04-28 08:09:45
    目录第一章 哈希表介绍第二章 哈希冲突第三章 哈希函数第四章 哈希表实现 ... 第一章 哈希表介绍 ...我们发现上述代码可以实现要求,但是空间复杂度极大,空间利用率极低,非常浪费内存空间,其实数组 c
  • 空间复杂度&nbsp;&nbsp; 尾递归 首先我们来理解一下算法的复杂度? &nbsp;&nbsp;算法的时间复杂度和空间复杂度统称为算法的复杂度。 时间复杂度是值执行算法所需要的计算工...
  • 时间复杂度和空间复杂度算法效率时间复杂度大O渐进表示法(估算)空间复杂度 什么是数据结构? 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 什么是...
  • 二分法搜索与哈希表

    2019-05-30 16:20:49
    在寻找排序数组中的某一个数字的时候可以使用二分法与哈希表的方式,哈希表时间复杂度是o(1),但是空间复杂度增大了,需要把所有存入哈希表内,而二分法就比较简单了,只需要进行折半查找。 哈希表: 从头到尾遍历...
  • 学会快速分析出算法的时间和空间复杂度!   目录: 1.哈希表基础知识复习 2.get第一次只出现一次的字符 3.从第一个字符串中删除所有在第二个字符串中出现过的字符 4.删除字符串中所有重复出现的字符(结果串...
  • (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度 在描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示...
  • 数组、链表、哈希表

    2020-06-20 21:36:33
    数组存储区间是连续的,占用内存严重,故空间复杂度大,但数组的二分查找时间复杂度小,为O(1), 数组的特点是:寻址容易,插入和删除困难 链表 链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度...
  • 哈希表的扩容实现机制导语哈希表什么是哈希表装载因子hashcode哈希冲突扩容方案Java中的实现Redis中的实现Objective-C中的实现结束语 导语 哈希表是实际开发中非常常用的数据结构,也很重要。了解其底层实现细节也...
  • 哈希表底层实现

    2021-01-20 13:46:03
    哈希表使用数组作为主干,实现查找,插入,删除元素的时间复杂度为O(1)。 哈希表(key,value) 就是把Key通过一个固定的算法函数既哈希函数转换成一个整型数字,然后将该数字对数组长度进行取余,取余结果就当作数组...
  • 内核中的哈希表

    2021-07-18 16:03:59
    知识点1、什么是哈希表2、什么是哈希表冲突3、如何解决哈希表冲突4、内核中哈希表的使用4.1 哈希表结构hlist 1、什么是哈希表 基本思想就是在关键字和其存储位置之间建立一种映射关系,实现时间复杂度0(1) 使用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 53,543
精华内容 21,417
关键字:

哈希表空间复杂度是多少