专栏首页营琪的小记录算法:哈希表HashTable-理论

算法:哈希表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 条评论
登录 后参与评论

相关文章

  • 算法:列表List、映射Map、集合Set-理论

    有很多类实现了List接口,我们比较熟悉的 ArrayList、LinkedList、Stack等等,我们从中选区ArrayList类观察一下源码,看看是怎么实...

    营琪
  • 复习:GoF的23种设计模式之Singleton模式(创建型)

    此模式也是我们不知不觉就会使用到的设计模式,例如我们将 配置文件映射为对象时,全局获取配置信息都使用此相同的对象。

    营琪
  • 关系数据库、数据库的设计(数据库学习)

    -|关系的数学定义:域(同类型值集合)、由笛卡儿积(任意域各自相乘)推出关系的定义

    营琪
  • JDK源码分析之集合04HashMap

    代码改变世界-coding
  • 如何设计并实现一个线程安全的 Map ?(上篇)

    Map 是一种很常见的数据结构,用于存储一些无序的键值对。在主流的编程语言中,默认就自带它的实现。C、C++ 中的 STL 就实现了 Map,JavaScrip...

    一缕殇流化隐半边冰霜
  • VR开发--Cardboard项目三:通过外置设备控制视野移动

    4-2:使用蓝牙的按键来控制第一人称的前后左右移动 其实Unity中已经为我们写好了控制一些按钮的事件.只需要测试一下就可以(Ps:因为每个蓝牙手柄的触发模式...

    雷潮
  • 【STM32F429的DSP教程】第10章 Matlab的WIFI通信实现

    本章节主要为大家讲解Matlab的WIFI方式波形数据传输和后期数据分析功能,非常实用。

    armfly
  • HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你!

    Map 这样的 Key Value 在软件开发中是非常经典的结构,常用于在内存中存放数据。

    端碗吹水
  • 【STM32F407的DSP教程】第10章 Matlab的WIFI通信实现

    本章节主要为大家讲解Matlab的WIFI方式波形数据传输和后期数据分析功能,非常实用。

    armfly
  • HashMap?ConcurrentHashMap?相信看完这篇没人能难住你!

    Map 这样的 Key Value 在软件开发中是非常经典的结构,常用于在内存中存放数据。

    Java团长

扫码关注云+社区

领取腾讯云代金券