HashTable（哈希表、散列表）

哈希表的定义

官方： 哈希表是根据关键码的值而直接访问的数据结构。 翻译：哈希表底层是一个数组，访问数据通过数组的下标进行访问。

哈希表的索引怎么产生

通过哈希函数产生索引的数据，使用哈希函数可以将不同的数据格式转化为不同的索引数值。 产生的索引数值超过了底层数组的长度，就会对索引数值进行取模操作，取模后的索引数值对应的数组位置上有存储对象，就会产生哈希碰撞。

如何解决哈希碰撞

两种方式 拉链法和线性探测法

拉链法 ： 将发生哈希冲突的对象，放在链表中。（要注意数组的长度和链表的长度，链表太长会浪费时间） 线性探测法： 如果哈希函数产生索引对应位置的位置有数据，那么就再这个位置的下面查找一个空位放数据（要保证哈希函数产生的索引大小小于底层数组长度的大小）

哈希表总结

使用场景： 快速判断一个元素是否出现过在集合里。 牺牲了空间换时间。

哈希表的算法题1

题目白话：判断两个字符串，条件：两个字符串中的内容只有字母顺序不同。 思路： 1建立一个数组a，大小为26（一共有26个字母），a下标为0，z下标为25，数组初始为0 2 将第一个字符串转化为字符数组b(toCharArray)，遍历数组b,数组a的下标确定为b[i]-‘a’ ，数组a的值加1 3 遍历另外一个字符串的字符数组，数组a的值-1 4 遍历数组a中是否有值不为0

for (char c : s.toCharArray()) {
          
   
            record[c - a] += 1;
        }

实现代码

public int[] intersection(int[] nums1, int[] nums2) {
          
   
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
          
   
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
          
   
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
          
   
            if (set1.contains(i)) {
          
   
                resSet.add(i);
            }
        }
        int[] resArr = new int[resSet.size()];
        int index = 0;
        //将结果几何转为数组
        for (int i : resSet) {
          
   
            resArr[index++] = i;
        }
        return resArr;
    }

java中的hash集合

java中的set集合

哈希表的算法题2

白话：将两个数组里面相同的部分抽取出来

思路： 1.将相同的部分抽取出来，并不需要排序 2.存放不同的内容的容器使用set HashSet

解题步骤 1.判断字符串是否为空或者为大小是否为0 || 连接 2.创建两个HashSet用于存储数据 3.将第一个数组里面数据遍历存入第一个HashSet 4.将第二个数组里面的数据遍历，用第一个HashSet的contain()判断是否存在，存在将数据存入第二个HashSet中 5.将数据存入一个数组中 new int[HashSet.size()]中

实现代码

public int[] intersection(int[] nums1, int[] nums2) {
          
   
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
          
   
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
          
   
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
          
   
            if (set1.contains(i)) {
          
   
                resSet.add(i);
            }
        }
        int[] resArr = new int[resSet.size()];
        int index = 0;
        //将结果几何转为数组
        for (int i : resSet) {
          
   
            resArr[index++] = i;
        }
        return resArr;
    }