本文共 3970 字，大约阅读时间需要 13 分钟。

哈希函数与哈希表

哈希函数是将任意大小的数据映射到固定大小值的函数，其返回值被称为哈希值或哈希码。这些值通常用于索引哈希表（Hash Table），一种以固定时间复杂度进行数据存取的数据结构。

为什么引入哈希表？

传统的数组索引查询速度很快，但无法直接将无序数据转化为数组索引查询。哈希表通过计算数据的哈希值来确定存储位置，实现了快速查找和插入操作。

哈希表的结构与特点

哈希表又称散列表，其主要特点是：

如何添加数据

添加数据的过程一般包括以下步骤：

如何查询数据

查询数据的过程与添加数据类似：

Java 中各种数据类型的哈希码计算

@Overridepublic int hashCode() {    return Integer.hashCode(value);}public static int hashCode(int value) {    return value;}

@Overridepublic int hashCode() {    return Double.hashCode(value);}public static int hashCode(double value) {    long bits = doubleToLongBits(value);    return (int)(bits ^ (bits >>> 32));}

public int hashCode() {    int h = hash;    if (h == 0 && value.length() > 0) {        char val[] = value;        for (int i = 0; i < value.length(); i++) {            h = 31 * h + val[i];        }        hash = h;    }    return h;}

@Overridepublic int hashCode() {    return Boolean.hashCode(value);}public static int hashCode(boolean value) {    return value ? 1231 : 1237;}

@Overridepublic int hashCode() {    return Long.hashCode(value);}public static int hashCode(long value) {    return (int)(value ^ (value >>> 32));}

public class User {    @TableId(type = IdType.ASSIGN_ID)    private Long id;    private String name;    private Integer age;    private String email;    @Override    public boolean equals(Object o) {        if (this == o) {            return true;        }        if (o == null || getClass() != o.getClass()) {            return false;        }        User user = (User) o;        return Objects.equals(id, user.id) &&                Objects.equals(name, user.name) &&                Objects.equals(age, user.age) &&                Objects.equals(email, user.email);    }    @Override    public int hashCode() {        return Objects.hash(id, name, age, email);    }}

如何减少冲突

哈希冲突不可避免，但可以通过设置合理的加载因子来减少冲突的概率。常见的加载因子为 0.75，即允许表记录数达到加载因子倍的容量时进行扩容。

HashMap 实现

JDK 1.7

HashMap 的核心是 Entry 类，每个节点包含：

• key 和 value。
• hash：存储节点的哈希码。
• next：指向下一个节点。

主要参数

• DEFAULT_INITIAL_CAPACITY：默认初始容量为 16。
• MAXIMUM_CAPACITY：哈希表最大容量为 2^30。
• DEFAULT_LOAD_FACTOR：默认加载因子为 0.75。
• threshold：扩容阈值。

初始化

public HashMap() {    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}

添加数据

public V put(K key, V value) {    if (table == EMPTY_TABLE) {        inflateTable(threshold);    }    if (key == null) {        return putForNullKey(value);    }    int hash = hash(key);    int i = indexFor(hash, table.length);    for (Entry e = table[i]; e != null; e = e.next) {        if (e.hash == hash && ((e.key == key) || (key != null && key.equals(e.key)))) {            e.value = value;            e.recordAccess(this);            return e.value;        }    }    modCount++;    addEntry(hash, key, value, i);    return null;}

扩容

private void inflateTable(int toSize) {    int capacity = roundUpToPowerOf2(toSize);    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);    table = new Entry[capacity];    initHashSeedAsNeeded(capacity);}

查询数据

public V get(Object key) {    if (key == null) {        return getForNullKey();    }    Entry entry = getEntry(key);    return entry != null ? entry.value : null;}

JDK 1.8

与 1.7 的主要区别是引入了红黑树来代替链表，当链表长度超过一定阈值时。

核心节点

public class Node implements Map.Entry
   
     {    final int hash;    final K key;    final V value;    Node next;}
   

主要参数

• TREEIFY_THRESHOLD：链表长度超过 8 时转为红黑树。
• UNTREEIFY_THRESHOLD：红黑树长度小于 6 时转回链表。
• MIN_TREEIFY_CAPACITY：哈希表容量超过 64 时允许链表转为红黑树。

查询数据

public V get(Object key) {    Node e = getNode(hash(key), key);    return e != null ? e.value : null;}

总结

哈希函数通过将任意数据映射到固定大小值实现高效的数据存取操作。哈希表通过哈希函数计算存储位置，实现了快速查找和插入。通过合理设置加载因子和优化链表结构，可以有效减少哈希冲突，提高哈希表的性能。

转载地址：http://bthwz.baihongyu.com/