哈希表 订阅
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。 展开全文
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
信息
作    用
直接进行访问的数据结构
别    名
散列表
中文名
哈希表
外文名
Hash table
哈希表基本概念
收起全文
精华内容
参与话题
问答
  • 哈希表

    千次阅读 2016-07-20 21:13:18
    哈希表

    哈希表

    1.      什么是哈希表?

    哈希表是一种数据结构,它提供了快速的插入操作和查找操作。其基于数据来实现。

    2.      哈希化

    (1)      直接将关键字作为索引。

    (2)      将单词转换为索引。

    a)        将字母转换为ASCII码,然后进行相加。

    b)        幂的连乘。

    c)        压缩可可选值。

    3.      压缩后仍然可能出现的问题:

    冲突,不能保证每个单词都映射到数组的空白单元。

    解决办法:

    (1)      开放地址法

    (2)      链地址法

    代码实现:

    /**
     * 员工信息类
     * @author Administrator
     *
     */
    public class Info {
    	private String key;  //工号
    	private String name;
    	
    	public Info(String key, String name) {
    		this.key = key;
    		this.name = name;
    	}
    
    	public String getKey() {
    		return key;
    	}
    
    	public void setKey(String key) {
    		this.key = key;
    	}
    
    	public String getName() {
    		return name;
    	}
    
    	public void setName(String name) {
    		this.name = name;
    	}
    	
    	
    }
    

    import java.math.BigInteger;
    
    public class HashTable {
    	private Info[] arr;
    	
    	/**
    	 * 默认的构造方法
    	 */
    	public HashTable() {
    		arr = new Info[100];
    	}
    	
    	/**
    	 * 指定数组初始化大小
    	 */
    	public HashTable(int maxSize) {
    		arr = new Info[maxSize];
    	}
    	
    	/**
    	 * 插入数据
    	 */
    	public void insert(Info info) {
    		arr[hashCode(info.getKey())] = info;
    	}
    	
    	/**
    	 * 查找数据
    	 */
    	public Info find(String key) {
    		return arr[hashCode(key)];
    	}
    	
    	public int hashCode(String key) {
    //		int hashVal = 0;
    //		for(int i = key.length() - 1; i >= 0; i--) {
    //			int letter = key.charAt(i) - 96;
    //			hashVal += letter;
    //		}
    //		return hashVal;
    		
    		BigInteger hashVal = new BigInteger("0");
    		BigInteger pow27 = new BigInteger("1");
    		for(int i = key.length() - 1; i >= 0; i--) {
    			int letter = key.charAt(i) - 96;
    			BigInteger letterB = new BigInteger(String.valueOf(letter));
    			hashVal = hashVal.add(letterB.multiply(pow27));
    			pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
    		}
    		return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
    	}
    }
    
    public class TestHashTable {
    	public static void main(String[] args) {
    		HashTable ht = new HashTable();
    		ht.insert(new Info("a","张三"));
    		ht.insert(new Info("ct","李四"));
    		ht.insert(new Info("wangwu","王五"));
    		
    		System.out.println(ht.find("a").getName());
    		System.out.println(ht.find("ct").getName());
    	}
    }
    
    运行结果:

    李四
    李四
    

    开放地址法

    1.什么是开发地址法?

             当冲突发生时,通过查找数组的一个空位,并将数据填入,而不再用哈希函数得到的数组下标,这个方法叫做开放地址法。

    2.数据的插入

    3.数据的查找

    4.数据的删除

    代码实现:

    /**
     * 员工信息类
     * @author Administrator
     *
     */
    public class Info {
    	private String key;
    	private String name;
    	
    	public Info(String key, String name) {
    		this.key = key;
    		this.name = name;
    	}
    
    	public String getKey() {
    		return key;
    	}
    
    	public void setKey(String key) {
    		this.key = key;
    	}
    
    	public String getName() {
    		return name;
    	}
    
    	public void setName(String name) {
    		this.name = name;
    	}
    	
    }
    import java.math.BigInteger;
    
    public class HashTable {
    	private Info[] arr;
    	
    	/**
    	 * 默认的构造方法
    	 */
    	public HashTable() {
    		arr = new Info[100];
    	}
    	
    	/**
    	 * 指定数组初始化大小
    	 */
    	public HashTable(int maxSize) {
    		arr = new Info[maxSize];
    	}
    	
    	/**
    	 * 插入数据
    	 */
    	public void insert(Info info) {
    		//获得关键字
    		String key = info.getKey();
    		//关键字所自定的哈希数
    		int hashVal = hashCode(key);
    		//如果这个索引已经被占用,而且里面是一个未被删除的数据
    		while(arr[hashVal] != null && arr[hashVal].getName() != null) {
    			//进行递加
    			++hashVal;
    			//循环
    			hashVal %= arr.length;
    		}
    		arr[hashVal] = info;
    	}
    	
    	/**
    	 * 查找数据
    	 */
    	public Info find(String key) {
    		int hashVal = hashCode(key);
    		while(arr[hashVal] != null) {
    			if(arr[hashVal].getKey().equals(key)) {
    				return arr[hashVal];
    			}
    			++hashVal;
    			hashVal %= arr.length;
    		}
    		return null;
    	}
    	
    	/**
    	 * 删除数据
    	 * @param key
    	 * @return
    	 */
    	public Info delete(String key) {
    		int hashVal = hashCode(key);
    		while(arr[hashVal] != null) {
    			if(arr[hashVal].getKey().equals(key)) {
    				Info tmp = arr[hashVal];
    				tmp.setName(null);
    				return tmp;
    			}
    			++hashVal;
    			hashVal %= arr.length;
    		}
    		return null;
    	}
    	
    	public int hashCode(String key) {
    //		int hashVal = 0;
    //		for(int i = key.length() - 1; i >= 0; i--) {
    //			int letter = key.charAt(i) - 96;
    //			hashVal += letter;
    //		}
    //		return hashVal;
    		
    		BigInteger hashVal = new BigInteger("0");
    		BigInteger pow27 = new BigInteger("1");
    		for(int i = key.length() - 1; i >= 0; i--) {
    			int letter = key.charAt(i) - 96;
    			BigInteger letterB = new BigInteger(String.valueOf(letter));
    			hashVal = hashVal.add(letterB.multiply(pow27));
    			pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
    		}
    		return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
    	}
    }
    
    public class TestHashTable {
    	public static void main(String[] args) {
    		HashTable ht = new HashTable();
    		ht.insert(new Info("a","张三"));
    		ht.insert(new Info("ct","李四"));
    		ht.insert(new Info("b","王五"));
    		
    		System.out.println(ht.find("a").getName());
    		System.out.println(ht.find("ct").getName());
    		System.out.println(ht.find("b").getName());
    		
    		ht.delete("b");
    		System.out.println(ht.find("b").getName());
    	}
    }

    运行结果:

    张三
    李四
    王五
    null
    

    链地址法

    1.什么是链地址法:

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

    1.      数据的插入

    2.      数据的查找

    3.      数据的删除

    代码的实现:

    /**
     * 员工信息类
     * @author Administrator
     *
     */
    public class Info {
    	private String key;
    	private String name;
    	
    	public Info(String key, String name) {
    		this.key = key;
    		this.name = name;
    	}
    
    	public String getKey() {
    		return key;
    	}
    
    	public void setKey(String key) {
    		this.key = key;
    	}
    
    	public String getName() {
    		return name;
    	}
    
    	public void setName(String name) {
    		this.name = name;
    	}
    	
    	
    }
    

    /*
     * 链结点,相当于是车厢
     */
    public class Node {
    	//数据域
    	public Info info;
    	//指针域
    	public Node next;
    	
    	public Node(Info info) {
    		this.info = info;
    	}
    	
    }
    
    /*
     * 链表,相当于火车
     */
    public class LinkList {
    	//头结点
    	private Node first;
    	
    	public LinkList() {
    		first = null;
    	}
    	
    	/**
    	 * 插入一个结点,在头结点后进行插入
    	 */
    	public void insertFirst(Info info) {
    		Node node = new Node(info);
    		node.next = first;
    		first = node;
    	}
    	
    	/**
    	 * 删除一个结点,在头结点后进行删除
    	 */
    	public Node deleteFirst() {
    		Node tmp = first;
    		first = tmp.next;
    		return tmp;
    	}
    	
    	
    	/**
    	 * 查找方法
    	 */
    	public Node find(String key) {
    		Node current = first;
    		while(!key.equals(current.info.getKey())) {
    			if(current.next == null) {
    				return null;
    			}
    			current = current.next;
    		}
    		return current;
    	}
    	
    	/**
    	 * 删除方法,根据数据域来进行删除
    	 */
    	public Node delete(String key) {
    		Node current = first;
    		Node previous = first;
    		while(!key.equals(current.info.getKey())) {
    			if(current.next == null) {
    				return null;
    			}
    			previous = current;
    			current = current.next;
    		}
    		
    		if(current == first) {
    			first = first.next;
    		} else {
    			previous.next = current.next;
    		}
    		return current;
    		
    	}
    }
    import java.math.BigInteger;
    
    public class HashTable {
    	private LinkList[] arr;
    	
    	/**
    	 * 默认的构造方法
    	 */
    	public HashTable() {
    		arr = new LinkList[100];
    	}
    	
    	/**
    	 * 指定数组初始化大小
    	 */
    	public HashTable(int maxSize) {
    		arr = new LinkList[maxSize];
    	}
    	
    	/**
    	 * 插入数据
    	 */
    	public void insert(Info info) {
    		//获得关键字
    		String key = info.getKey();
    		//关键字所自定的哈希数
    		int hashVal = hashCode(key);
    		if(arr[hashVal] == null) {
    			arr[hashVal] = new LinkList();
    		}
    		arr[hashVal].insertFirst(info);
    	}
    	
    	/**
    	 * 查找数据
    	 */
    	public Info find(String key) {
    		int hashVal = hashCode(key);
    		return arr[hashVal].find(key).info;
    	}
    	
    	/**
    	 * 删除数据
    	 * @param key
    	 * @return
    	 */
    	public Info delete(String key) {
    		int hashVal = hashCode(key);
    		return arr[hashVal].delete(key).info;
    	}
    	
    	public int hashCode(String key) {
    //		int hashVal = 0;
    //		for(int i = key.length() - 1; i >= 0; i--) {
    //			int letter = key.charAt(i) - 96;
    //			hashVal += letter;
    //		}
    //		return hashVal;
    		
    		BigInteger hashVal = new BigInteger("0");
    		BigInteger pow27 = new BigInteger("1");
    		for(int i = key.length() - 1; i >= 0; i--) {
    			int letter = key.charAt(i) - 96;
    			BigInteger letterB = new BigInteger(String.valueOf(letter));
    			hashVal = hashVal.add(letterB.multiply(pow27));
    			pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
    		}
    		return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
    	}
    }
    	public static void main(String[] args) {
    		HashTable ht = new HashTable();
    		ht.insert(new Info("a","张三"));
    		ht.insert(new Info("ct","李四"));
    		ht.insert(new Info("b","王五"));
    		ht.insert(new Info("dt","赵柳"));
    		
    		System.out.println(ht.find("a").getName());
    		System.out.println(ht.find("ct").getName());
    		System.out.println(ht.find("b").getName());
    		System.out.println(ht.find("dt").getName());
    		
    //		System.out.println(ht.hashCode("a"));
    //		System.out.println(ht.hashCode("ct"));
    		
    		System.out.println(ht.delete("a").getName());
    		System.out.println(ht.find("a").getName());
    
    	}
    }
    运行结果:

    张三
    李四
    王五
    赵柳
    张三
    Exception in thread "main" java.lang.NullPointerException
    	at ch17.HashTable.find(HashTable.java:41)
    	at ch17.TestHashTable.main(TestHashTable.java:20)
    











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

    万次阅读 多人点赞 2018-06-28 17:27:37
    一、哈希表概述  首先简单介绍几个概念:哈希表(散列表)、映射、冲突、链地址、哈希函数。  哈希表(Hash table)的初衷是为了将数据映射到数组中的某个位置,这样就能够通过数组下标访问该数据,提高数据的...

    一、哈希表概述

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

           哈希表(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)

     

     

     

    展开全文
  • 数据结构 Hash表(哈希表

    万次阅读 多人点赞 2018-05-20 01:23:34
    要想知道什么是哈希表,那得先了解哈希函数 哈希函数 对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引与查找值进行比较。那么,有没有一种...

    参考链接:数据结构(严蔚敏)

    一、什么是Hash表

    要想知道什么是哈希表,那得先了解哈希函数
    哈希函数

    对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引与查找值进行比较。那么,有没有一种函数H,根据这个函数和查找关键字key,可以直接确定查找值所在位置,而不需要一个个比较。这样就**“预先知道”**key所在的位置,直接找到数据,提升效率。

    地址index=H(key)
    说白了,hash函数就是根据key计算出应该存储地址的位置,而哈希表是基于哈希函数建立的一种查找表

    二、哈希函数的构造方法

    根据前人经验,统计出如下几种常用hash函数的构造方法:
    直接定制法
    哈希函数为关键字的线性函数如 H(key)=a*key+b
    这种构造方法比较简便,均匀,但是有很大限制,仅限于地址大小=关键字集合的情况
    使用举例:
    假设需要统计中国人口的年龄分布,以10为最小单元。今年是2018年,那么10岁以内的分布在2008-2018,20岁以内的分布在1998-2008……假设2018代表2018-2008直接的数据,那么关键字应该是2018,2008,1998……
    那么可以构造哈希函数H(key)=(2018-key)/10=201-key/10
    那么hash表建立如下

    index key 年龄 人数(假设数据)
    0 2018 0-10 200W
    1 2008 10-20 250W
    2 1998 20-30 253W
    3 1988 30-40 300W
    ……

    数字分析法
    假设关键字集合中的每个关键字key都是由s位数字组成(k1,k2,,knk_1,k_2,……,k_n),分析key中的全体数据,并从中提取分布均匀的若干位或他们的组合构成全体

    使用举例
    我们知道身份证号是有规律的,现在我们要存储一个班级学生的身份证号码,假设这个班级的学生都出生在同一个地区,同一年,那么他们的身份证的前面数位都是相同的,那么我们可以截取后面不同的几位存储,假设有5位不同,那么就用这五位代表地址。
    H(key)=key%100000
    此种方法通常用于数字位数较长的情况,必须数字存在一定规律,其必须知道数字的分布情况,比如上面的例子,我们事先知道这个班级的学生出生在同一年,同一个地区。
    平方取中法
    如果关键字的每一位都有某些数字重复出现频率很高的现象,可以先求关键字的平方值,通过平方扩大差异,而后取中间数位作为最终存储地址。
    使用举例
    比如key=1234 1234^2=1522756 取227作hash地址
    比如key=4321 4321^2=18671041 取671作hash地址
    这种方法适合事先不知道数据并且数据长度较小的情况
    折叠法
    如果数字的位数很多,可以将数字分割为几个部分,取他们的叠加和作为hash地址
    使用举例
    比如key=123 456 789
    我们可以存储在61524,取末三位,存在524的位置
    该方法适用于数字位数较多且事先不知道数据分布的情况
    除留余数法用的较多
    H(key)=key MOD p (p<=m m为表长)
    很明显,如何选取p是个关键问题。

    使用举例
    比如我们存储3 6 9,那么p就不能取3
    因为 3 MOD 3 == 6 MOD 3 == 9 MOD 3
    p应为不大于m的质数或是不含20以下的质因子的合数,这样可以减少地址的重复(冲突)

    比如key = 7,39,18,24,33,21时取表长m为9 p为7 那么存储如下

    index 0 1 2 3 4 5 6 7 8
    key 7 21(冲突后移) 24 4 18(冲突后移) 33冲突后移)
    **随机数法** H(key) =Random(key) 取关键字的随机函数值为它的散列地址

    hash函数设计的考虑因素

    1.计算散列地址所需要的时间(即hash函数本身不要太复杂)
    2.关键字的长度
    3.表长
    4.关键字分布是否均匀,是否有规律可循
    5.设计的hash函数在满足以上条件的情况下尽量减少冲突

    三、哈希冲突

    即不同key值产生相同的地址,H(key1)=H(key2)
    比如我们上面说的存储3 6 9,p取3是
    3 MOD 3 == 6 MOD 3 == 9 MOD 3
    此时3 6 9都发生了hash冲突

    哈希冲突的解决方案

    不管hash函数设计的如何巧妙,总会有特殊的key导致hash冲突,特别是对动态查找表来说。
    hash函数解决冲突的方法有以下几个常用的方法
    1.开放定制法
    2.链地址法
    3.公共溢出区法
    建立一个特殊存储空间,专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
    4.再散列法
    准备若干个hash函数,如果使用第一个hash函数发生了冲突,就使用第二个hash函数,第二个也冲突,使用第三个……
    重点了解一下开放定制法和链地址法

    开放定制法

    首先有一个H(key)的哈希函数
    如果H(key1)=H(keyi)
    那么keyi存储位置Hi=(H(key)+di)MODmH_i=(H(key)+d_i)MOD mm为表长
    did_i有三种取法
    1)线性探测再散列
    di=cid_i=c*i
    2)平方探测再散列
    di=12,12,22,22d_i=1^2,-1^2,2^2,-2^2……
    3)随机探测在散列(双探测再散列)
    did_i是一组伪随机数列
    注意
    增量di应该具有以下特点(完备性):产生的Hi(地址)均不相同,且所产生的s(m-1)个Hi能覆盖hash表中的所有地址

    • 平方探测时表长m必须为4j+3的质数(平方探测表长有限制)
    • 随机探测时m和di没有公因子(随机探测di有限制)
      三种开放定址法解决冲突方案的例子

    废话不多说,上例子就明白了
    有一组数据
    19 01 23 14 55 68 11 86 37要存储在表长11的数组中,其中H(key)=key MOD 11
    那么按照上面三种解决冲突的方法,存储过程如下:
    (表格解释:从前向后插入数据,如果插入位置已经占用,发生冲突,冲突的另起一行,计算地址,直到地址可用,后面冲突的继续向下另起一行。最终结果取最上面的数据(因为是最“占座”的数据))
    线性探测再散列
    我们取di=1,即冲突后存储在冲突后一个位置,如果仍然冲突继续向后

    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 14 19 86
    23冲突 23
    68冲突 68冲突 68
    11冲突 11冲突 11冲突 11冲突 11冲突 11
    37冲突 37冲突 37
    最终存储结果 55 1 23 14 68 11 37 19 86
    **平方探测再散列**
    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 14 37 19 86
    23冲突 H(23)+1
    H(68)-1冲突 68冲突 H(68)+1冲突 H(68)+4
    11冲突 H(11)+1冲突 H(11)-1
    最终存储结果 55 1 23 14 37 68 19 86 11
    **随机探测在散列(双探测再散列)** 发生冲突后 H(key)‘=(H(key)+di)MOD m 在该例子中 H(key)=key MOD 11 我们取di=key MOD 10 +1 则有如下结果:
    index 0 1 2 3 4 5 6 7 8 9 10
    key 55 1 68 14 19 86
    23冲突 H(23)+3+1
    11冲突 H(11)+1+1冲突 H(11)+1+1+1+1
    (H(37)+8)模11冲突 37冲突 (H(37)+8+8+8)模11 (H(37)+8+8)模11冲突
    最终存储结果 55 1 68 14 23 11 37 19 86

    链地址法

    产生hash冲突后在存储数据后面加一个指针,指向后面冲突的数据
    上面的例子,用链地址法则是下面这样:

    这里写图片描述
    四、hash表的查找

    查找过程和造表过程一致,假设采用开放定址法处理冲突,则查找过程为:
    对于给定的key,计算hash地址index = H(key)
    如果数组arr【index】的值为空 则查找不成功
    如果数组arr【index】== key 则查找成功
    否则 使用冲突解决方法求下一个地址,直到arr【index】== key或者 arr【index】==null

    hash表的查找效率

    决定hash表查找的ASL因素:
    1)选用的hash函数
    2)选用的处理冲突的方法
    3)hash表的饱和度,装载因子 α=n/m(n表示实际装载数据长度 m为表长)
    一般情况,假设hash函数是均匀的,则在讨论ASL时可以不考虑它的因素
    hash表的ASL是处理冲突方法和装载因子的函数
    前人已经证明,查找成功时如下结果:

    这里写图片描述
    可以看到无论哪个函数,装载因子越大,平均查找长度越大,那么装载因子α越小越好?也不是,就像100的表长只存一个数据,α是小了,但是空间利用率不高啊,这里就是时间空间的取舍问题了。通常情况下,认为α=0.75是时间空间综合利用效率最高的情况。

    上面的这个表可是特别有用的。假设我现在有10个数据,想使用链地址法解决冲突,并要求平均查找长度<2
    那么有1+α/2 <2
    α<2
    即 n/m<2 (n=10)
    m>10/2
    m>5 即采用链地址法,使得平均查找长度< 2 那么m>5

    之前我的博客讨论过各种树的平均查找长度,他们都是基于存储数据n的函数,而hash表不同,他是基于装载因子的函数,也就是说,当数据n增加时,我可以通过增加表长m,以维持装载因子不变,确保ASL不变。
    那么hash表的构造应该是这样的:

    这里写图片描述
    五、hash表的删除

    首先链地址法是可以直接删除元素的,但是开放定址法是不行的,拿前面的双探测再散列来说,假如我们删除了元素1,将其位置置空,那 23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据,比如-1

    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 44,927
精华内容 17,970
关键字:

哈希表