哈希表概述

  • 哈希表的特点：key → value 键值对
  • 实例：存储操作学号姓名表

image.png
方式一：数组，key 为索引 value 为数组值
image.png
方式二：Java 封装好的 HashMap
9_Java集合

哈希表的四种操作

  • 访问 Access ×
  • 搜索 Search 时间复杂度 O(1)
    查 key，如果考虑哈希碰撞，时间复杂度为 O(k)，其中 k 为碰撞元素的个数
  • 插入 Insert 时间复杂度 O(1)

key → 哈希得到内存地址 → 插入 value

  • 删除 Remove 时间复杂度 O(1)
    通过 key 删除

哈希表实际的常用操作（Java）

  • 创建哈希表

    1.       //Create HashTable by Array 
    2.       String[] hashTable = new String[4];
    3.       //Create HashTable by HashMap lib 
    4.       HashMap<Integer, String> map = new HashMap<>();

  • 添加元素

    1.       //Add element
    2.       //Time Complexity:O(1)
    3.       hashTable[1] = "hanmeimei";
    4.       hashTable[2] = "lihua";
    5.       hashTable[3] = "siyangyuan";
    6.       map.put(1, "hanmeimei");
    7.       map.put(2, "lihua");
    8.       map.put(3, "siyangyuan");

  • 更新元素

    1.       //Update element
    2.       //Time Complexity:O(1)
    3.       hashTable[1] = "bishi";
    4.       map.put(1, "bishi");

  • 删除元素

    1.       //Remove element
    2.       //Time Complexity:O(1)
    3.       hashTable[1] = "";
    4.       map.remove(1);

  • 获取元素

    1.       //Get Value
    2.       //Time Complexity:O(1)
    3.       String temp = hashTable[3];
    4.       map.get(3);

  • 检查 key 是否存在

    1.       //Check key
    2.       //Time Complexity:O(1)
    3.       //hashTable check the length 
    4.       map.containsKey(3);

  • 哈希表长度

    1.       //Length
    2.       //Time Complexity:O(1)
    3.       //hashTable Size variables 
    4.       map.size();

  • 哈希表是否还有元素

    1.       //Is Empty?
    2.       //Time Complexity:O(1)
    3.       //hashTable Size variables 
    4.       map.isEmpty();

LeetCode练习

#217

#389

#496

参考：https://www.bilibili.com/read/cv8716169?spm_id_from=333.788.b_636f6d6d656e74.22