散列表介绍介绍

散列表是什么

散列表（Hash Table），也称为哈希表、散列映射或字典，是一种数据结构，它以键值对的形式存储数据，通过对键进行哈希计算，得到对应的存储位置，从而实现快速的查找、插入和删除操作。

散列表通常由一个数组和一个哈希函数组成。哈希函数将键映射到数组的索引位置，这个索引位置就是该键在散列表中对应的存储位置。由于哈希函数的设计和实现不同，可能会出现哈希冲突（即不同的键映射到了同一个索引位置），这种情况需要使用某种冲突解决方法，常见的有链表法和开放地址法。

散列表的优点是在平均情况下，查找、插入和删除操作的时间复杂度为O(1)，即常数时间内完成，因此在处理大量数据时具有高效性。然而，在最坏情况下，哈希冲突可能导致散列表的性能下降，时间复杂度会退化到线性时间复杂度O(n)，因此在散列表的设计和实现中，需要考虑如何尽可能地避免哈希冲突。

HashTable代码实现

import java.util.ArrayList;

class HashTable{
    class HashEntry{
        String key;
        int value;
        HashEntry next;
        public HashEntry(String key, int value)
        {
            this.key = key;
            this.value = value;
        }
    }
    
	private ArrayList<HashEntry> bucket;
	private int slots;
	private int size;

	public HashTable(){
		bucket = new ArrayList <HashEntry>();
		slots = 5;
		size = 0;
		for (int i = 0; i < slots; i++)
			bucket.add(null);
	}

	public int size() { return size; }
	public boolean isEmpty() { return size() == 0; }

    private int getIndex(String key){
		int hashCode = key.hashCode();
		int index = hashCode % slots;
		return index;
	}

	public int delete(String key){
        int b_Index = getIndex(key);
            HashEntry head = bucket.get(b_Index);
            HashEntry prev = null;
            while (head != null){
                if (head.key.equals(key))
                    break;
                prev = head;
                head = head.next;
            }
    
            if (head == null)
                return 0;
            size--;
            if (prev != null)
                prev.next = head.next;
            else
                bucket.set(b_Index, head.next);
            return head.value;
        }

    public int get(String key){
		int b_Index = getIndex(key);
		HashEntry head = bucket.get(b_Index);
		while (head != null){
			if (head.key.equals(key))
				return head.value;
			head = head.next;
		}
		return 0;
	}

	public void insert(String key, int value){	
		int b_Index = getIndex(key);
		HashEntry head = bucket.get(b_Index);
		while (head != null){
			if (head.key.equals(key)){
				head.value = value;
				return;
			}
			head = head.next;
		}
		size++;
		head = bucket.get(b_Index);
		HashEntry new_slot = new HashEntry(key, value);
		new_slot.next = head;
		bucket.set(b_Index, new_slot);

		if ((1.0*size)/slots >= 0.6){
			ArrayList <HashEntry> temp = bucket;
			bucket = new ArrayList<>();
			slots = 2 * slots;
			size = 0;
			for (int i = 0; i < slots; i++)
				bucket.add(null);
			for (HashEntry head_Node : temp){
				while (head_Node != null){
					insert(head_Node.key, head_Node.value);
					head_Node = head_Node.next;
				}
			}
		}
	}
}