算法:哈希表HashTable-理论

哈希表,我们平时好像用到的不多,使用HashMap的时候,才间接的使用到了,在信息安全领域用到的比较多(文件效验、数字签名),下面我们先来看看哈希函数。

哈希函数:将任意长度的数据映射到有限长度的域上,就是对一串数据m进行杂糅,输出另一段固定长度的数据h,作为这段数据的特征。类似的MD5算法也是一种哈希函数。

例如String.hashCode

    package java.lang.String;
    private int hash; // Default to 0
    private final char value[];/** The value is used for character storage. */
    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

通过这个String的哈希函数,我们可以得到一个字符串的哈希值。

当我们建立一张表,通过哈希运算得到一个固定长度的值,把字符串和哈希值一一对应上,这张表就叫做哈希表。

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

例如下面这张图,哈希函数为:key=(字母ASCII码相加)取30的模。

我们设计的哈希函数太过于简单,那么通过哈希运算后得到的值等于20的还有很多(foes等等),类似的,当一个哈希值不唯一对于一个数据时,我们称发生了哈希碰撞。

解决哈希碰撞有几种方法,方法很多,下面只是列举常用的。

1.例如上图,在发生碰撞的位置建立链表,把数据分别存入链表中,这种方法叫做拉链法。

2. 开放寻址法:Hi=(H(key) + di) MOD m,i=1,2,…,k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列。

3.再散列法:建立多个不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。

Java中的hashtable是怎么实现的?

    public Hashtable() {                                        //构造函数
        this(11, 0.75f);
    }
    public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];                        //创建一个Entry数组,保存键值对。
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

    private static class Entry<K,V> implements Map.Entry<K,V> {        //主要保存的对象的地方
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;
    ...//getKey、getValue、setValue、equals、hashCode、toString方法。
    }

    public synchronized V put(K key, V value) {                       //添加方法
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;                                    //初始化时,生成的对象
        int hash = key.hashCode();                                   //获取key的哈希值
        int index = (hash & 0x7FFFFFFF) % tab.length;                //位运算,获取数组下标
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];                  
        for(; entry != null ; entry = entry.next) {                  //判断当前下标数组是否为空,即哈希冲突
            if ((entry.hash == hash) && entry.key.equals(key)) {     //链接法,解决哈希冲突
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);                           //没哈希冲突,调用
        return null;
    }

    private void addEntry(int hash, K key, V value, int index) {     //实际添加方法
        modCount++;

        Entry<?,?> tab[] = table;
        if (count >= threshold) {                                    //数组是否有空间
            // Rehash the table if the threshold is exceeded
            rehash();                                                //扩容

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];                    //下一个Entry先设置为空
        tab[index] = new Entry<>(hash, key, value, e);             //保存键值对数据到Enetry对象,并设置Next下一个为空。
        count++;
    }

HashTable 的实现,先创建Entry数组,Entry对象负责保存数据。put方法,先检查保存前的必要检查工作,后面调用实际添加数据方法;如果检查到哈希冲突,则通过链接法解决哈希冲突;调用实际添加数据方法中需要检查数组是否有空间,是否需要扩容,以及保存数据生成Entry对象,讲生成的Entry对象保存进数组中。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券