JAVA数据结构之哈希表「建议收藏」

hash表的优缺点hash表比树形结构快的原因,表的是位置是计算出来的通过hash函数,满足随机插入的结构。但是在有该优点的情况下,需要考虑哈希冲突本例结构中采用链地址法【在hash表的每一个表单元,都是链表结构,发生冲突的元素,自动加入链表】在jdk8以前采用的是链表解决,在jdk8之后,在处理哈希冲突时,先采用链表,当链表中size大于8时,转化为树形结构,…

大家好,又见面了,我是你们的朋友全栈君。

hash表的优缺点

hash表比树形结构快的原因,表的是位置是计算出来的通过hash函数,满足随机插入的结构。但是在有该优点的情况下,需要考虑哈希冲突

本例结构中采用链地址法【在hash表的每一个表单元,都是链表结构,发生冲突的元素,自动加入链表】

在jdk8以前采用的是链表解决,在jdk8之后,在处理哈希冲突时,先采用链表,当链表中size大于8时,转化为树形结构,采用的红黑树结构。

这里写图片描述
这里写图片描述

//不需要像二分搜索树一样 键值实现可比较,只需要能实现hashCode 但每一个对象都是继承自Object 所以都有hashCode方法
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];
        this.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;//消除掉key对应的hashCode的符号
    }

    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 + "doesn't exist");
        } else {
            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;//在hash()中会用到新的的M
        //必须重新给M赋值!!!
        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;
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/126574.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号