数据结构===散列表

简介: 数据结构===散列表

概要

散列表是一种很有趣的数据结构。

散列表是一个很有用的数据结构。它是数组演练而来的,又是一个基于数组的扩展的数据结构。接下来看看。

散列思想

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

散列表是由key和hash组成的。

散列函数

散列函数很重要的,牵扯到后边的散列冲突。

构造散列函数,三点基本要求:

  1. 散列函数计算得到的散列值是一个非负整数
  2. 如果key1 = key2,那么hash(key1) == hash(key2)
  3. 如果key1 != key2, 那么hash(key1) != hash(key2)
    散列冲突无法完全避免。散列函数的应用挺多的,像MD5,SHA,CRC等等,都是应用了散列函数。接下来看看散列冲突。

散列冲突

散列冲突无法避免。

散列冲突无法避免,那我们聊聊散列冲突怎么解决。通常由2种方式,及开放寻址法和链表法。

开放寻址法

基于数组的解决方案。

开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。其中有线性检测,二次探测,双重散列。其中,不管哪种,如果列表空闲位置不多,都会增加散列冲突发生的概率。为了减小散列冲突发生的概率,一般都会保证有一定比例的空闲槽位。用装载因子表示空闲槽位的多少。

装载因子

计算公式:

散列表的装载因子=填入表中的元素个数/散列表的长度

这个也更重要。

链表法

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。也就是一个槽位对应一个链表。这就不难,当散列表效率最差的时候,就退化成链表了。当然,如果比较均匀,它的效果还是很好的。

代码Java

public class HashTable<K, V> {
    /**
     * 散列表默认长度
     */
    private static final int DEFAULT_INITAL_CAPACITY = 8;
    /**
     * 装载因子
     */
    private static final float LOAD_FACTOR = 0.75f;
    /**
     * 初始化散列表数组
     */
    private Entry<K, V>[] table;
    /**
     * 实际元素数量
     */
    private int size = 0;
    /**
     * 散列表索引数量
     */
    private int use = 0;
    public HashTable() {
        table = (Entry<K, V>[]) new Entry[DEFAULT_INITAL_CAPACITY];
    }
    static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;
        Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    /**
     * 新增
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        int index = hash(key);
        // 位置未被引用,创建哨兵节点
        if (table[index] == null) {
            table[index] = new Entry<>(null, null, null);
        }
        Entry<K, V> tmp = table[index];
        // 新增节点
        if (tmp.next == null) {
            tmp.next = new Entry<>(key, value, null);
            size++;
            use++;
            // 动态扩容
            if (use >= table.length * LOAD_FACTOR) {
                resize();
            }
        }
        // 解决散列冲突,使用链表法
        else {
            do {
                tmp = tmp.next;
                // key相同,覆盖旧的数据
                if (tmp.key == key) {
                    tmp.value = value;
                    return;
                }
            } while (tmp.next != null);
            Entry<K, V> temp = table[index].next;
            table[index].next = new Entry<>(key, value, temp);
            size++;
        }
    }
    /**
     * 散列函数
     * <p>
     * 参考hashmap散列函数
     *
     * @param key
     * @return
     */
    private int hash(Object key) {
        int h;
        return (key == null) ? 0 : ((h = key.hashCode()) ^ (h >>> 16)) % table.length;
    }
    /**
     * 扩容
     */
    private void resize() {
        Entry<K, V>[] oldTable = table;
        table = (Entry<K, V>[]) new Entry[table.length * 2];
        use = 0;
        for (int i = 0; i < oldTable.length; i++) {
            if (oldTable[i] == null || oldTable[i].next == null) {
                continue;
            }
            Entry<K, V> e = oldTable[i];
            while (e.next != null) {
                e = e.next;
                int index = hash(e.key);
                if (table[index] == null) {
                    use++;
                    // 创建哨兵节点
                    table[index] = new Entry<>(null, null, null);
                }
                table[index].next = new Entry<>(e.key, e.value, table[index].next);
            }
        }
    }
    /**
     * 删除
     *
     * @param key
     */
    public void remove(K key) {
        int index = hash(key);
        Entry e = table[index];
        if (e == null || e.next == null) {
            return;
        }
        Entry pre;
        Entry<K, V> headNode = table[index];
        do {
            pre = e;
            e = e.next;
            if (key == e.key) {
                pre.next = e.next;
                size--;
                if (headNode.next == null) use--;
                return;
            }
        } while (e.next != null);
    }
    /**
     * 获取
     *
     * @param key
     * @return
     */
    public V get(K key) {
        int index = hash(key);
        Entry<K, V> e = table[index];
        if (e == null || e.next == null) {
            return null;
        }
        while (e.next != null) {
            e = e.next;
            if (key == e.key) {
                return e.value;
            }
        }
        return null;
    }
}

小结

散列表学习总结

散列表是一种基于数组数据结构。有key和hash组成。重点是散列冲突如何解决,怎么减少散列碰撞发生的概率,设计装载因子和散列函数。如何解决散列冲突呢?有开放寻址法和链表法2种方法。然后就是看看java如何实现的,当然也有其他语言的,只是没有一一列举出来。关键是算法学会了,什么语言实现都不重要了。

相关文章
|
11月前
|
存储 缓存 数据库
Python高级数据结构——散列表(Hash Table)
Python高级数据结构——散列表(Hash Table)
111 1
Python高级数据结构——散列表(Hash Table)
|
存储 算法 NoSQL
【数据结构和算法】散列表的查找算法(开放地址法,链地址法)
【数据结构和算法】散列表的查找算法(开放地址法,链地址法)
410 0
【数据结构和算法】散列表的查找算法(开放地址法,链地址法)
|
5月前
|
存储 算法
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
89 0
|
6月前
|
存储 缓存 索引
【数据结构入门精讲 | 第十四篇】散列表知识点及考研408、企业面试练习(1)
【数据结构入门精讲 | 第十四篇】散列表知识点及考研408、企业面试练习(1)
87 0
|
6月前
|
自然语言处理 数据安全/隐私保护
【数据结构入门精讲 | 第十五篇】散列表知识点及考研408、企业面试练习(2)
【数据结构入门精讲 | 第十五篇】散列表知识点及考研408、企业面试练习(2)
50 0
|
6月前
|
存储 算法 索引
Python 数据结构和算法:什么是散列表(Hash Table)?在 Python 中如何实现?
Python 数据结构和算法:什么是散列表(Hash Table)?在 Python 中如何实现?
66 0
|
存储 算法 Java
Java数据结构与算法分析(十一)散列表(哈希表)
散列表(Hash Table)也叫哈希表,是根据给定关键字(Key)来计算出该关键字在表中存储地址的数据结构。也就是说,散列表建立了关键字与存储地址之间的一种直接映射关系,将关键字映射到表中记录的地址,这加快了查找速度。
180 0
|
存储 Java Serverless
数据结构系列: Hash散列表
一个函数。我们可以把它定义成hash(key),其中 key 表示元素的键值,hash(key) 的值表示经过散列函数计算得到的散列值。
146 0
数据结构系列: Hash散列表
|
C语言
c语言《数据结构》散列表(哈希表)
c语言《数据结构》散列表(哈希表)
153 0
|
存储 Serverless 索引
408数据结构学习笔记——B树、B+树、散列表
408数据结构学习笔记——B树、B+树、散列表
292 1
408数据结构学习笔记——B树、B+树、散列表