hash表

亦凉 2022-02-01 15:57 213阅读 0赞

1、开始
    public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
    继承了类HashMap，实现了Map接口
    
    2、属性
    
        //双向链表，用于记录所有的元素
        private transient Entry<K,V> header;
    
        //遍历顺序【访问顺序或插入顺序】，默认插入顺序
        private final boolean accessOrder;
    
    
    3、双向链表
    
         private static class Entry<K,V> extends HashMap.Entry<K,V> {
             //双向链表中的上一个节点before和下一个节点after
            Entry<K,V> before, after;
    
            Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
                super(hash, key, value, next);
            }
    
            //从双向链表中删除元素
            private void remove() {
                //改变当前节点的前后两个节点的引用关系，若当前节点没有被引用，则才可以被GC回收
                //将前一个节点的after指向后一个节点
                before.after = after;
                //将后一个节点的before指向前一个节点
                after.before = before;
            }
    
            //将当前节点插入到指定节点的链表中，即指定节点的前面
            private void addBefore(Entry<K,V> existingEntry) {
                //指定当前节点与前后节点的引用关系
                //将当前节点的后一个节点指向指定节点
                after  = existingEntry;
                //将当前节点的前一个节点指向指定节点的前一个节点
                before = existingEntry.before;
    
                //指定前后节点与当前节点的引用关系
                //当前节点的前一个节点的后一个节点就是当前节点
                before.after = this;
                //当前节点的后一个节点的前一个节点就是当前节点
                after.before = this;
            }
    
               //查询或修改元素时调用
            void recordAccess(HashMap<K,V> m) {
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
                if (lm.accessOrder) {
                    //当时按访问顺序时，即最近较少使用顺序LRU
                    lm.modCount++;
                    //删除当前节点
                    remove();
                    //当当前节点添加到链表尾部
                    addBefore(lm.header);
                }
            }
    
            //删除元素时调用
            void recordRemoval(HashMap<K,V> m) {
                remove();
            }
        }
    
    4、构造器
    
        //指定容量和加载因子，遍历顺序为插入顺序
        public LinkedHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor);
            accessOrder = false;
        }
        //默认加载因子，遍历顺序为插入顺序
        public LinkedHashMap(int initialCapacity) {
            super(initialCapacity);
            accessOrder = false;
        }
        //默认初始化容量和加载因子，遍历顺序为插入顺序
        public LinkedHashMap() {
            super();
            accessOrder = false;
        }
        //添加元素用于初始化，遍历顺序为插入顺序
        public LinkedHashMap(Map<? extends K, ? extends V> m) {
            super(m);
            accessOrder = false;
        }
        //指定容量和加载因子，以及遍历顺序
        public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }
    
        //构造对象时，初始化双向链表
        @Override
        void init() {
            //初始化头节点
            header = new Entry<>(-1, null, null, null);
            //头结点即是其自身的前一个也是后一个
            header.before = header.after = header;
        }
    
    5、添加
    
        //添加时，重写了HashMap的此方法
         void addEntry(int hash, K key, V value, int bucketIndex) {
            super.addEntry(hash, key, value, bucketIndex);
    
            //头结点的第一个节点
            Entry<K,V> eldest = header.after;
            if (removeEldestEntry(eldest)) {
                //删除第一个节点
                removeEntryForKey(eldest.key);
            }
        }
    
        //新增节点
        void createEntry(int hash, K key, V value, int bucketIndex) {
            //获取老链表
            HashMap.Entry<K,V> old = table[bucketIndex];
            //新增节点
            Entry<K,V> e = new Entry<>(hash, key, value, old);
            //添加到数组中
            table[bucketIndex] = e;
            //当前节点添加到头结点尾部，添加使用前插法
            e.addBefore(header);
            //计数
            size++;
        }
    
        //是否删除第一个节点，即老的节点
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return false;
        }
    
    6、查找
    
        public V get(Object key) {
            Entry<K,V> e = (Entry<K,V>)getEntry(key);
            if (e == null)
                return null;
            //记录查找的元素，用于根据访问的顺序时，维护双向链表
            e.recordAccess(this);
            return e.value;
        }
    
    参考资料：
    http://www.cnblogs.com/tstd/p/5059589.html

以上内容来自于[https://www.cnblogs.com/xiaoxian1369/p/5634050.html][https_www.cnblogs.com_xiaoxian1369_p_5634050.html]

\-------------------------

hash表其实是一个映射，即按照键和值的方式来存储——一个值k要存在内存中，他的地址由f(k)来决定，这个f(k)只要不超过地址范围即可。

且Hash函数是单向不可逆的，所以有很高的可靠性。

运用范围很广尤其在信息科学领域，比较经典的一个就是文件MD5码校验。

当然最根本的还是加快查找速度啦

现实中[哈希函数][Link 1]是需要构造的，并且构造的好才能使用的好。

\-------------------------

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

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

现实中[哈希函数][Link 1]是需要构造的，并且构造的好才能使用的好。

百度搬运工已上线hhhhhhh[https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E8%A1%A8/5981869?fr=aladdin][https_baike.baidu.com_item_E5_93_88_E5_B8_8C_E8_A1_A8_5981869_fr_aladdin]

[https_www.cnblogs.com_xiaoxian1369_p_5634050.html]: https://www.cnblogs.com/xiaoxian1369/p/5634050.html
[Link 1]: https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0
[Link 2]: https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E8%A1%A8/10027933
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450
[Link 4]: https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B0/2366288
[Link 5]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097
[https_baike.baidu.com_item_E5_93_88_E5_B8_8C_E8_A1_A8_5981869_fr_aladdin]: https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E8%A1%A8/5981869?fr=aladdin