哈希冲突在Java中是如何解决的

在Java中，哈希冲突通常是通过开放寻址法（open addressing）和链地址法（separate chaining）这两种方法来解决的。

1. 开放寻址法： 开放寻址法是一种线性探测的方法，当发生哈希冲突时，它会按照一定的规律（如线性探测、二次探测或双散列）在哈希表中寻找下一个可用的空槽位。以下是线性探测的简单示例：

public class LinearProbingHashTable {
    private int size;
    private int[] table;

    public LinearProbingHashTable(int size) {
        this.size = size;
        this.table = new int[size];
    }

    public void put(int key, int value) {
        int index = getIndex(key);
        while (table[index] != 0) {
            if (table[index] == key) {
                table[index] = value;
                return;
            }
            index = (index + 1) % size;
        }
        table[index] = key;
    }

    public int get(int key) {
        int index = getIndex(key);
        while (table[index] != 0) {
            if (table[index] == key) {
                return table[index];
            }
            index = (index + 1) % size;
        }
        return -1; // 表示键不存在
    }

    private int getIndex(int key) {
        return key % size;
    }
}

2. 链地址法： 链地址法是通过在哈希表的每个槽位上维护一个链表来解决哈希冲突的方法。当发生哈希冲突时，新的元素会被添加到对应槽位的链表中。以下是链地址法的简单示例：

public class ChainingHashTable {
    private int size;
    private static class Entry {
        int key;
        int value;
        Entry next;

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

    private Entry[] table;

    public ChainingHashTable(int size) {
        this.size = size;
        this.table = new Entry[size];
    }

    public void put(int key, int value) {
        int index = getIndex(key);
        Entry entry = table[index];
        if (entry == null) {
            table[index] = new Entry(key, value);
            return;
        }
        while (entry != null) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
            if (entry.next == null) {
                break;
            }
            entry = entry.next;
        }
        entry.next = new Entry(key, value);
    }

    public int get(int key) {
        int index = getIndex(key);
        Entry entry = table[index];
        while (entry != null) {
            if (entry.key == key) {
                return entry.value;
            }
            entry = entry.next;
        }
        return -1; // 表示键不存在
    }

    private int getIndex(int key) {
        return key % size;
    }
}

这两种方法各有优缺点，开放寻址法在空间利用上更高效，但可能导致聚集问题；链地址法在插入和删除操作上性能较好，但需要额外的内存来存储链表节点。在实际应用中，可以根据具体需求选择合适的哈希冲突解决方法。