加入收藏 | 设为首页 | 会员中心 | 我要投稿 上饶站长网 (https://www.0793zz.com.cn/)- 数据库平台、视觉智能、智能搜索、决策智能、迁移!
当前位置: 首页 > 服务器 > 安全 > 正文

自己动手实现java数据结构(五)哈希表

发布时间:2021-04-01 04:35:00 所属栏目:安全 来源:网络整理
导读:1.哈希表介绍 前面我们已经介绍了许多类型的数据结构。在想要查询容器内特定元素时,有序向量使得我们能使用二分查找法进行精确的查询(( O(logN)对数复杂度,很高效 )。 可人类总是不知满足,依然在寻求一种更高效的特定元素查询的数据结构, 哈希表/散列表(
副标题[/!--empirenews.page--]

1.哈希表介绍

  前面我们已经介绍了许多类型的数据结构。在想要查询容器内特定元素时,有序向量使得我们能使用二分查找法进行精确的查询((O(logN)对数复杂度,很高效)。
  可人类总是不知满足,依然在寻求一种更高效的特定元素查询的数据结构,哈希表/散列表(hash table)就应运而生啦。哈希表在特定元素的插入,删除和查询时都能够达到O(1)常数的时间复杂度,十分高效。

1.1 哈希算法

  哈希算法的定义:把任意长度的输入通过哈希算法转换映射为固定长度的输出,所得到的输出被称为哈希值(hashCode =?hash(input))。哈希映射是一种多对一的关系,即多个不同的输入有可能对应着一个相同的哈希值输出;也意味着,哈希映射是不可逆,无法还原的。

  举个例子:我们有一个好朋友叫熊大,大家都叫他老熊。可以理解为是一个hash算法:对于一个人名,我们一般称呼为"老" + 姓氏(单姓) (hash(熊大) = 老熊)。同时,我们还有一个好朋友叫熊二,我们也叫他老熊(hash(熊二) = 老熊)。当熊大和熊二两个好朋友同时和我们聚会时,都称呼他们为老熊就不太合适啦,因为这时出现了hash冲突。老熊这个称呼同时对应了多个人,多个不同的输入对应了相同的哈希值输出。

  java在Object这一最高层对象中实现了hashCode方法,并允许子类重写更适应自身,冲突概率更低的hashCode方法。

1.2 哈希表实现的基本思路

  哈希表存储的是key-value键值对结构的数据,其基础是一个数组。

  由于采用hash算法会出现hash冲突,一个数组下标对应了多个元素。常见的解决hash冲突的方法有:开放地址法、重新哈希法、拉链法等等,我们的哈希表实现采用的是拉链法解决hash冲突。

  采用拉链法的哈希表将内部数组的每一个元素视为一个插槽(slot)或者桶(bucket),并将数据存放在键值对节点(EntryNode)中。EntryNode除了存放key和value,还维护着一个next节点的引用。为了解决hash冲突,单个插槽内的多个EntryNode构成一个简单的单向链表,插槽指向链表的头部节点,新的数据将会插入当前链表的尾部。

  key值不同但映射的hash值相同的元素在哈希表的同一个插槽中以链表的形式共存。

  

自己动手实现java数据结构(五)哈希表

1.3 哈希表的负载因子(loadFactor):

  哈希表在查询数据时通过直接计算数据hash值对应的插槽,迅速获取到key值对应的数据,进行非常高效的数据查询。

  但依然存在一个问题:虽然设计良好的hash函数可以尽可能的降低hash冲突的概率,但hash冲突还是不可避免的。当发生频繁的哈希冲突时,对应的插槽内可能会存放较多的元素,导致插槽内的链表数据过多。而链表的查询效率是非常低的,在极端情况下,甚至会出现所有元素都映射存放在同一个插槽内,此时的哈希表退化成了一个链表,查询效率急剧降低。

  一般的,哈希表存储的数据量一定时,内部数组的大小和数组插槽指向的链表长度成反比。换句话说,总数据量一定,内部数组的容量越大(插槽越多),平均下来桶链表的长度也就越小,查询效率越高。

  同等数据量下,哈希表内部数组容量越大,查询效率越高,但同时空间占用也越高,这本质上是一个空间换时间的取舍。

  哈希表允许用户在初始化时指定负载因子(loadFactor):负载因子代表着存储的总数据量和内部数组大小的比值。插入新数据时,判断哈希表当前的存储量和内部数组的比值是否超过了负载因子。当比值超过了负载因子时,哈希表认为内部过于拥挤,查询效率太低,会触发一次扩容的rehash操作。rehash会对内部数组扩容,将存储的元素重新进行hash映射,使得哈希表始终保持一个合适的查询效率。

  通过指定自定义的负载因子,用户可以控制哈希表在空间和时间上取舍的程度,使哈希表能更有效地适应用户的使用场景。

  指定的负载因子越大,哈希表越拥挤(负载高,紧凑),查询效率越低,空间效率越高。

  指定的负载因子越小,哈希表越稀疏(负载小,松散),查询效率越高,空间效率越低。

2.哈希表ADT接口

  和之前介绍的链表不同,我们在哈希表的ADT接口中暴露出了哈希表内部实现的EntryNode键值对节点。通过暴露出去的public方法,用户在使用哈希表时,可以获得内部的键值对节点,灵活的访问其中的key、value数据(但没有暴露setKey方法,不允许用户自己设置key值)。

public interface Map <K,V>{
    /**
     * 存入键值对
     * @param key   key值
     *  value value
     * @return 被覆盖的的value值
     */
    V put(K key,V value);

    
     * 移除键值对
     *  被删除的value的值
     
    V remove(K key);

    
     * 获取key对应的value值
     *       对应的value值
     
    V get(K key);

    
     * 是否包含当前key值
     *       true:包含 false:不包含
     */
    boolean containsKey(K key);

    
     * 是否包含当前value值
     *  value   value值
     *         true:包含 false:不包含
      containsValue(V value);

    
     * 获得当前map存储的键值对数量
     *  键值对数量
     * int size();

    
     * 当前map是否为空
     *   true:为空 false:不为空
      isEmpty();

    
     * 清空当前map
     void clear();

    
     * 获得迭代器
     *  迭代器对象
     
    Iterator<EntryNode<K,V>> iterator();

    
     * 键值对节点 内部类
     * class EntryNode<K,1)">{
        final K key;
        V value;
        EntryNode<K,1)"> next;

        EntryNode(K key,V value) {
            this.key = key;
            this.value = value;
        }

         keyIsEquals(K key){
            if(this.key == key){
                return true;
            }

            if(key == null){
                //:::如果走到这步,this.key不等于null,不匹配
                false;
            }else{
                return key.equals(this.key);
            }
        }

        EntryNode<K,1)"> getNext() {
            return next;
        }

        void setNext(EntryNode<K,1)"> next) {
            this.next =public K getKey() {
             key;
        }

         V getValue() {
             setValue(V value) {
             value;
        }

        @Override
         String toString() {
            return key + "=" + value;
        }
    }
}

3.哈希表实现细节

3.1 哈希表基本属性:      

class HashMap<K,V> implements Map<K,1)">{

    
     * 内部数组
     * private EntryNode<K,1)">[] elements;

    
     * 当前哈希表的大小
     * private  size;

    
     * 负载因子
     * float loadFactor;

    
     * 默认的哈希表容量
     * final static int DEFAULT_CAPACITY = 16;

    
     * 扩容翻倍的基数
     * int REHASH_BASE = 2
     * 默认的负载因子
     * float DEFAULT_LOAD_FACTOR = 0.75f========================================构造方法===================================================
    
     * 默认构造方法
     * 
    @SuppressWarnings("unchecked")
     HashMap() {
        this.size = 0;
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        elements = new EntryNode[DEFAULT_CAPACITY];
    }

    
     * 指定初始容量的构造方法
     *  capacity 指定的初始容量
     * public HashMap( capacity) {
         EntryNode[capacity];
    }

    
     * 指定初始容量和负载因子的构造方法
     *  capacity 指定的初始容量
     *  loadFactor 指定的负载因子
     * int capacity, loadFactor) {
         loadFactor;
        elements =  EntryNode[capacity];
    }
}

3.2 通过hash值获取对应插槽下标:

  获取hash的方法仅和数据自身有关,不受到哈希表存储数据量的影响。

(编辑:上饶站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

热点阅读