数据结构之散列表(数组和链表的结合)的读写操作(Java)「数据结构 散列表」
散列表(Hash Table)是一种数据结构,它结合了数组和链表的特点,在散列表中,数据以键值对的形式存储,每个键对应一个值,通过哈希函数将键映射到数组的一个位置,如果该位置已经有其他键值对存在,则使用链表来解决冲突。
读写操作是散列表的基本操作之一,下面是散列表的读写操作的Java实现:
![数据结构之散列表(数组和链表的结合)的读写操作(Java)「数据结构 散列表」-图1 数据结构之散列表(数组和链表的结合)的读写操作(Java)「数据结构 散列表」-图1](http://wq21.cn/zb_users/upload/2024/05/20240528155608_18358.png)
// 定义散列表节点类 class HashNode<K, V> { K key; V value; HashNode<K, V> next; public HashNode(K key, V value) { this.key = key; this.value = value; this.next = null; } } // 定义散列表类 class HashTable<K, V> { private int capacity; // 散列表的容量 private HashNode<K, V>[] table; // 存储键值对的数组 public HashTable(int capacity) { this.capacity = capacity; table = new HashNode[capacity]; } // 哈希函数,用于计算键的哈希值 private int hash(K key) { return (key.hashCode() & 0x7fffffff) % capacity; } // 插入操作 public void put(K key, V value) { int index = hash(key); // 计算键的哈希值对应的数组下标 HashNode<K, V> node = table[index]; // 获取该位置的链表头节点 // 如果该位置没有节点,直接插入新节点 if (node == null) { table[index] = new HashNode<>(key, value); return; } // 如果该位置有节点,遍历链表查找是否已存在相同键的节点 while (node != null) { if (node.key.equals(key)) { // 如果找到相同键的节点,更新其值并返回 node.value = value; return; } else { node = node.next; // 如果未找到相同键的节点,继续遍历链表 } } // 如果遍历完整个链表仍未找到相同键的节点,说明发生了冲突,需要将新节点插入链表尾部 node.next = new HashNode<>(key, value); } // 读取操作 public V get(K key) { int index = hash(key); // 计算键的哈希值对应的数组下标 HashNode<K, V> node = table[index]; // 获取该位置的链表头节点 // 如果该位置没有节点,说明不存在该键,返回null或抛出异常根据需求而定 while (node != null) { if (node.key.equals(key)) { // 如果找到相同键的节点,返回其值并结束循环 return node.value; } else { node = node.next; // 如果未找到相同键的节点,继续遍历链表 } } return null; // 如果遍历完整个链表仍未找到相同键的节点,返回null或抛出异常根据需求而定 } }
上述代码实现了一个简单的散列表类`HashTable`,其中包含了插入操作`put`和读取操作`get`,在插入操作中,首先通过哈希函数计算出键的哈希值对应的数组下标,然后根据该下标在数组中找到对应的链表头节点,如果该位置没有节点,直接在该位置插入新节点;如果该位置已经有节点,遍历链表查找是否已存在相同键的节点,如果找到则更新其值并返回,否则将新节点插入链表尾部,在读取操作中,同样先通过哈希函数计算出键的哈希值对应的数组下标,然后根据该下标在数组中找到对应的链表头节点,如果该位置没有节点,说明不存在该键,返回null或抛出异常根据需求而定;如果该位置有节点,遍历链表查找是否已存在相同键的节点,如果找到则返回其值并结束循环,否则返回null或抛出异常根据需求而定。
![数据结构之散列表(数组和链表的结合)的读写操作(Java)「数据结构 散列表」-图2 数据结构之散列表(数组和链表的结合)的读写操作(Java)「数据结构 散列表」-图2](http://wq21.cn/zb_users/upload/2024/05/20240528155611_30383.png)