09 HashTable与HashMap

2024 年 7 月 22 日 星期一

09 HashTable与HashMap

HashMap:

基本概念

HashMap是Java集合框架中基于哈希表(Hash Table)实现的键值对(Key-Value)存储结构。它允许存储null值和null键,并且不保证元素的顺序。HashMap是非线程安全的,如果需要线程安全的操作,可以使用ConcurrentHashMap`或者通过Collections工具类将其包装为线程安全的版本。

主要特点

  1. 快速访问:由于基于哈希表实现,HashMap能够在O(1)时间复杂度内完成插入和查找操作(在理想情况下)。
  2. 无序存储HashMap不保证存储顺序,元素的顺序可能在插入时和取出时不同。
  3. 允许null键和null值:一个HashMap实例可以存储一个null键和多个null值。

    ### 实现原理

HashMap的实现依赖于哈希表和链表。每个键值对存储在一个称为Node的内部类中,Node`包含四个属性:键、值、哈希值和下一个节点的引用。当存储元素时,通过键的哈希值确定元素在哈希表中的位置(桶),如果发生哈希冲突,则通过链表或红黑树(在链表长度超过一定阈值时)来解决冲突。

  1. 哈希函数HashMap使用键的hashCode()方法生成哈希值,并通过哈希函数将其映射到数组的索引位置。
  2. 碰撞处理:当两个键的哈希值映射到同一位置时,HashMap使用链表将这些键值对串联起来。在Java 8及以后版本,当链表长度超过一定阈值(默认8)时,会将链表转换为红黑树,以提高查找效率。

主要方法

以下是HashMap中常用的方法及其功能:

  1. put(K key, V value):将指定的键值对插入到HashMap中。如果键已存在,则更新对应的值。 java 复制代码 HashMap<String, Integer> map = new HashMap<>(); map.put("one", 1); map.put("two", 2);
  2. get(Object key):根据键获取对应的值,如果键不存在则返回null。 java 复制代码 Integer value = map.get("one"); // 返回1
  3. remove(Object key):根据键删除对应的键值对,并返回被删除的值。 java 复制代码 Integer removedValue = map.remove("one"); // 返回1
  4. containsKey(Object key):检查HashMap是否包含指定的键。 java 复制代码 boolean contains = map.containsKey("two"); // 返回true
  5. containsValue(Object value):检查HashMap是否包含指定的值。 java 复制代码 boolean contains = map.containsValue(2); // 返回true
  6. size():返回HashMap中键值对的数量。 java 复制代码 int size = map.size(); // 返回1
  7. isEmpty():检查HashMap是否为空。 java 复制代码 boolean isEmpty = map.isEmpty(); // 返回false
  8. clear():清空HashMap,移除所有键值对。 java 复制代码 `map.clear();

示例代码 ​

HashMap的基本使用:
``` import java.util.HashMap; import java.util.Map;

public class HashMapExample { public static void main(String[] args) { // 创建一个HashMap实例 HashMap<String, Integer> map = new HashMap<>();

    // 添加键值对
    map.put("one", 1);
    map.put("two", 2);
    map.put("three", 3);

    // 获取值
    Integer value = map.get("two");
    System.out.println("Value for key 'two': " + value);

    // 检查是否包含键或值
    boolean hasKey = map.containsKey("three");
    boolean hasValue = map.containsValue(3);
    System.out.println("Contains key 'three': " + hasKey);
    System.out.println("Contains value 3: " + hasValue);

    // 移除键值对
    Integer removedValue = map.remove("one");
    System.out.println("Removed value: " + removedValue);

    // 遍历HashMap
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
    }

    // 清空HashMap
    map.clear();
    System.out.println("Map is empty: " + map.isEmpty());
}

} ```

这个示例展示如何创建一个HashMap实例、添加键值对、获取值、检查包含关系、移除键值对、遍历HashMap以及清空HashMap
​ ​

HashTable : ​

基本概念

Hashtable是Java集合框架中的一个类,提供了一种基于哈希表的数据结构,用于存储键值对。Hashtable实现了Map接口,类似于HashMap,但有几个关键区别,最重要的是Hashtable`是线程安全的,它的所有方法都是同步的。

主要特点

  1. 线程安全Hashtable中的所有方法都是同步的,因此它是线程安全的,适合多线程环境。
  2. 不允许null键和null值Hashtable不允许存储null键或null值,如果尝试存储,将抛出NullPointerException
  3. 无序存储:和HashMap一样,Hashtable不保证元素的顺序。

实现原理

Hashtable的实现依赖于哈希表和链表。每个键值对存储在一个称为Entry的内部类中,Entry`包含四个属性:键、值、哈希值和下一个节点的引用。当存储元素时,通过键的哈希值确定元素在哈希表中的位置(桶),如果发生哈希冲突,则通过链表解决冲突。

  1. 哈希函数Hashtable使用键的hashCode()方法生成哈希值,并通过哈希函数将其映射到数组的索引位置。
  2. 碰撞处理:当两个键的哈希值映射到同一位置时,Hashtable使用链表将这些键值对串联起来。

主要方法


以下是Hashtable中常用的方法及其功能:

  1. put(K key, V value):将指定的键值对插入到Hashtable中。如果键已存在,则更新对应的值。  
    java  
    复制代码  
    Hashtable<String, Integer> table = new Hashtable<>();   table.put("one", 1);   table.put("two", 2);
  2. get(Object key):根据键获取对应的值,如果键不存在则返回null。  
    java  
    复制代码  
    Integer value = table.get("one"); // 返回1
  3. remove(Object key):根据键删除对应的键值对,并返回被删除的值。  
    java  
    复制代码  
    Integer removedValue = table.remove("one"); // 返回1
  4. containsKey(Object key):检查Hashtable是否包含指定的键。  
    java  
    复制代码  
    boolean contains = table.containsKey("two"); // 返回true
  5. contains(Object value):检查Hashtable是否包含指定的值。  
    java  
    复制代码  
    boolean contains = table.contains(2); // 返回true
  6. size():返回Hashtable中键值对的数量。  
    java  
    复制代码  
    int size = table.size(); // 返回1
  7. isEmpty():检查Hashtable是否为空。  
    java  
    复制代码  
    boolean isEmpty = table.isEmpty(); // 返回false
  8. clear():清空Hashtable,移除所有键值对。  
    java  
    复制代码  
    `table.clear();  

示例代码

import java.util.Hashtable;
import java.util.Map;

public class HashtableExample {
    public static void main(String[] args) {
        // 创建一个Hashtable实例
        Hashtable<String, Integer> table = new Hashtable<>();

        // 添加键值对
        table.put("one", 1);
        table.put("two", 2);
        table.put("three", 3);

        // 获取值
        Integer value = table.get("two");
        System.out.println("Value for key 'two': " + value);

        // 检查是否包含键或值
        boolean hasKey = table.containsKey("three");
        boolean hasValue = table.contains(3);
        System.out.println("Contains key 'three': " + hasKey);
        System.out.println("Contains value 3: " + hasValue);

        // 移除键值对
        Integer removedValue = table.remove("one");
        System.out.println("Removed value: " + removedValue);

        // 遍历Hashtable
        for (Map.Entry<String, Integer> entry : table.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }

        // 清空Hashtable
        table.clear();
        System.out.println("Table is empty: " + table.isEmpty());
    }
}
  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...