代码随想录-java-哈希表总结

哈希表定义：���列表（Hash table），是根据关键码值（Key-value）而直接进行访问的数据结构。

常见的哈希结构：数组；map（映射）；set（集合）。

目录

• 一.不同哈希结构的对应方法
• • 1.数组
  • 2.HashMap
  • 3.HashSet
  • 二.题目解决思路和实现代码
  • • 1.有效的字母异位词（242）
    • 2.两个数组交集（349）
    • 3.快乐数（202）
    • 4.两数之和（1）
    • 5.四数相加Ⅱ（454）
    • 6.赎金信（383）
    • 7.三数之和（15）
    • 8.四数之和（18）

      一.不同哈希结构的对应方法

      1.数组

      如图可见，数组中key就是索引下标，value就是元素。数组是最简单的哈希结构。

      2.HashMap

      HashMap的基本操作：增删改查

      需注意：HashMap中key值具有唯一性，所以若put重复的key值，则会覆盖value值。

      创建：

      //创建HashMap（以key为整数，value为字符串为例）HashMap mymap=new HashMap(); 

      添加：

      //存入key-value对mymap.put(1,"google"); 

      查询：

      //通过key得到value值String value1=mymap.get(key);

      删除：

      //通过key删除key-value对mymap.remove(key);//删除全部元素mymap.clear();

      改值：

      //改变key值对应的value值mymap.replace(key,new_value); 

      判断：

      //通过key值判断是否有某个键值对的存在boolean flag1=mymap.containsKey(key);//通过value值判断是否有某个键值对的存在boolean flag2=mymap.containsValue(value);

      遍历hashmap的键值对:

      HashMap myhashmap = new HashMap();for(Map.Entry my : myhashmap.entry()){my.getKey();my.getValue();}

      得到全部value（返回一个集合）：

      myhashmap.values()

      3.HashSet

      HashSet的基本操作：增删改查

      需注意：HashSet可以自动去重

      创建：

      //创建HashSet（以元素为整数为例）HashSet myset=new HashSet(); 

      添加：

      //存入元素myset.add(1); 

      删除：

      //删除某个元素myset.remove(1);//删除全部元素myset.clear();

      判断：

      //判断是否有某个元素的存在boolean flag=myset.contains(1);

      二.题目解决思路和实现代码

      1.有效的字母异位词（242）

      题目：

      给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

      注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。且 s 和 t 仅包含小写字母

      分析和解决思路：

      分析：

      1.s和t互为字母异位词，则必须s和t的字符串长度一致。

      2.由于字符串中仅包含小写字母，字符又有ASCII表的十进制数。则字符串中每个字符减去‘a’就可以得到一个数字（可以代表在小写字母表中的位置）。

      3.数组就是一个哈希表，理解为一个字母表。

      解决思路：

      1.创建一个长度为26的数组（初始元素值均为默认零值），索引代表字母（字母位置），元素代表字母出现的次数。在遍历s和t字符串过程中，s中出现的字母让数组字母位置的元素+1；s中出现的数组字母让字母位置的元素-1。

      2.最后检查数组，若全为零元素，则说明s和t中每个字符出现的次数都相同。返回true。

      实现代码：

      class Solution {    public boolean isAnagram(String s, String t) {        //先判断长度是否一样，不一样则一定是false        if(s.length()!=t.length()) return false;        //数组也是一个哈希表        int[] z_table=new int[26]; //创建一个26长的初始化全为0的数字数组        for(int i=0;i            z_table[s.charAt(i)-'a']++; //当s中存在该字母时，对应位置数字加一            z_table[t.charAt(i)-'a']--; //当s中存在该字母时，对应位置数字加一        }        for(int i=0;i            //对这个字母表进行检验，如果全都是0，则说明两个是一样的            if(z_table[i]!=0){                return false;            }        }        return true;    }}