当前位置：首页 > article >正文

Hash算法与Hash冲突

article 2024/11/20 17:34:25

一、Hash算法

哈希算法是一种将任意长度的输入（通常是一个字符串）通过某种计算转换成固定长度的输出的算法。这种转换过程被称为哈希函数，而输出的结果通常被称为哈希值或哈希码。

Hash算法的特点:

确定性：相同的输入总是产生相同的输出
快速计算：对于给定的输入，可以快速计算出哈希值。
抗碰撞性：对于不同的输入，很难找到两个不同的输入产生相同的输出。
随机性：哈希值看起来应该是随机的，没有明显的模式。

在Java中，哈希算法可以通过多种方式实现，包括使用Java标准库中的HashMap类，或者自定义哈希函数和数据结构。

二、Hash冲突

    哈希冲突是指不同的输入值经过哈希函数处理后得到了相同的输出值。理论上，由于哈希函数的输出空间是有限的，而输入空间是无限的，所以哈希冲突在某些情况下是不可避免的。但在实际应用中，一个好的哈希函数会尽量减少冲突的发生。


处理哈希冲突的办法：

开放寻址法：当发生冲突时，算法会在哈希表中寻找下一个空闲位置来存储数据。
链地址法：每个哈希表的槽位都对应一个链表，所有映射到同一个槽位的元素都存储在这个链表中。
双重哈希：使用两个哈希函数，当第一个哈希函数产生冲突时，使用第二个哈希函数来计算下一个可能的位置。
再哈希法：使用一组哈希函数，当发生冲突时，使用另一个哈希函数重新计算哈希值。

哈希算法在数据存储、密码学、快速查找等领域有着广泛的应用。选择一个好的哈希算法对于确保数据的安全性和效率至关重要。

三、自定义Hash算法示例

1、定义Hash函数

我们可以使用一个简单的哈希函数，比如将输入字符串的每个字符的ASCII值相加，然后对一个固定的大小取模。

public class SimpleHashFunction {
    public static int hash(String key, int tableSize) {
        int hashValue = 0;
        for (char c : key.toCharArray()) {
            hashValue += c;
        }
        return hashValue % tableSize;
    }
}

2、创建哈希表

哈希表可以用一个数组来实现，数组的每个元素是一个链表，用于存储具有相同哈希值的元素。

import java.util.LinkedList;
import java.util.List;

public class HashTable {

    private List<LinkedList<Entry>> table;

    /**
     * 构造函数，初始化哈希表
     */
    public HashTable(int size) {
        table = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            table.add(new LinkedList<>());
        }
    }

    /**
     * 插入数据
     * @param key 键
     * @param value 值
     */
    public void insert(String key, int value) {

        //计算hash值
        int index = SimpleHashFunction.hash(key, table.size());

        //以计算的hash值作为索引，在hash表根据索引获取对应的链表，并对链表进行遍历
        for (Entry entry : table.get(index)) {

            //如果链表中的entry存在相同的键，则更新值
            if (entry.getKey().equals(key)) {
                // 更新已有键的值
                entry.setValue(value);
                return;
            }
        }

        //如果链表中没有相同的键，则创建新的entry对象，并将它添加到链表中
        table.get(index).add(new Entry(key, value));
    }

    /**
     * 查找数据
     * @param key 键
     * @return 键对应的值，如果未找到则返回-1
     */
    public int get(String key) {
        int index = SimpleHashFunction.hash(key, table.size());
        for (Entry entry : table.get(index)) {
            if (entry.getKey().equals(key)) {
                return entry.getValue();
            }
        }
        return -1;  // 返回-1表示未找到
    }

    /**
     * 删除数据
     * @param key 键
     * @return 存在该键并删除则返回true，否则返回false
     */
    public boolean delete(String key) {
        int index = SimpleHashFunction.hash(key, table.size());
        for (Entry entry : table.get(index)) {
            if (entry.getKey().equals(key)) {
                table.get(index).remove(entry);
                return true;
            }
        }
        return false;
    }

    private static class Entry {
        private String key;
        private int value;

        public Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }

        public String getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }
}

3、使用Hash表

我们可以创建一个哈希表实例，并使用它来插入、搜索和删除数据。

public class TestHash {

    public static void main(String[] args) {
        HashTable hashTable = new HashTable(10);

        // 插入数据
        hashTable.insert("apple", 1);
        hashTable.insert("banana", 2);
        hashTable.insert("cherry", 3);

        // 搜索数据
        System.out.println(hashTable.get("apple"));  // 输出: 1

        // 删除数据
        hashTable.delete("banana");
        System.out.println(hashTable.get("banana"));  // 输出: -1
    }
}