概要
散列表是一种很有趣的数据结构。
散列表是一个很有用的数据结构。它是数组演练而来的,又是一个基于数组的扩展的数据结构。接下来看看。
散列思想
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。
散列表是由key和hash组成的。
散列函数
散列函数很重要的,牵扯到后边的散列冲突。
构造散列函数,三点基本要求:
- 散列函数计算得到的散列值是一个非负整数
- 如果key1 = key2,那么hash(key1) == hash(key2)
- 如果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如何实现的,当然也有其他语言的,只是没有一一列举出来。关键是算法学会了,什么语言实现都不重要了。