哈希：更高效的查找！

面试必问的HashMap

我们在开发的过程中经常会用到HashMap来保存键值对，实现的主要思路，就是通过hash函数确定对应的key应该放在数组的哪个位置。

当要放的位置发生冲突时，就需要解决冲突，一般情况下有两种如下方法

1. 开放寻址法（当要放的位置上有值的时候，依次找数组的下一个位置，看是否有空位）
2. 链表法（用链表存储发生冲突的元素）

当我们想要保证放入的key有序时，我们就可以用LinkedHashMap，LinkedHashMap=哈希表+双向链表 哈希算法在Java中的应用有集合类HashMap，HashSet等，本质上就是用来保存映射关系的

但保存映射关系的数据结构不只有哈希表，数组也可以。计数排序不就用数组的下标i以及其对应的值a[i]来表示值为i的数有a[i]个

输出频率最高且最先出现的字符

假设有一个字符串，字符串内部的所有字符都是在ascii编码的范围内，编码求出字符串中出现频率最高的字符，如果频率最高的字符有几个字符出现的频率一样，则输出最先出现的字符。

如输入串为 “hello world, every body!”，则输出频率最高且最先出现的字符

我们可以通过哈希表这种结构得到每个字符出现的频率，但是当最高的字符出现频率一样时，需要输出最先出现的字符，应该如何保存这种顺序呢？

我们用LinkedHashMap不就能同时保存字符出现的顺序和字符出现的频率了吗？

public char getMaxOccurChar(String str) {

    int maxCount = 1;
    Character result = new Character(str.charAt(0));

    Map<Character, Integer> map = new LinkedHashMap<>();
    for (int i = 0; i < str.length(); i++) {
        Character content = str.charAt(i);
        map.put(content, map.getOrDefault(content, 0) + 1);
    }

    for (Map.Entry<Character, Integer> entry: map.entrySet()) {
        if (entry.getValue() > maxCount) {
            maxCount = entry.getValue();
            result = entry.getKey();
        }
    }
    return result;
}

遍历两次，第一次遍历将字符的出现频率放入哈希表中。第二次遍历哈希表，找出出现频率最高的字符。

有没有可能一次遍历解决这个问题呢？ 正着一边遍历一边比较大小试试看？

public char getMaxOccurChar(String str) {

    int maxCount = 1;
    Character result = new Character(str.charAt(0));

    Map<Character, Integer> map = new LinkedHashMap<>();

    for (int i = 0; i < str.length() ; i++) {
        Character content = str.charAt(i);
        Integer count = map.getOrDefault(content, 0);
        map.put(content, count + 1);
        if (count + 1 >= maxCount) {
            maxCount = count + 1;
            result = content;
        }
    }
    return result;
}

这种会有什么问题呢？如果输入的字符串是aaaccc，则最终的输出是c，不是a，不符合题意。 发现是程序中count + 1 >= maxCount中的>=造成的，我们把>=改成>不就行了。 如果把>=改为，针对如下输入baab，最终的输出是a，不是b，不符合题意

倒着遍历可以解决这个问题吗？

public char getMaxOccurChar(String str) {

    int maxCount = 1;
    Character result = new Character(str.charAt(0));

    Map<Character, Integer> map = new LinkedHashMap<>();

    for (int i = str.length() - 1; i >= 0 ; i--) {
        Character content = str.charAt(i);
        Integer count = map.getOrDefault(content, 0);
        map.put(content, count + 1);
        if (count + 1 >= maxCount) {
            maxCount = count;
            result = content;
        }
    }
    return result;
}

当然可以，通过倒序来保证最终求出的结果是最先出现的

最长连续序列

题目地址：LeetCode 128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例1

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

因为题目要求O(n)的时间复杂度，所以不能排序。我们可以遍历每个数num，假设它是某个序列的开头，那么需要满足num-1不在数组中，然后从num+1开始递增，查找对应的数是否在数组中。通过打擂台的方式求出最长连续序列。

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    int max = 0;
    for (int num : nums) {
        if (!set.contains(num - 1)) {
            int sum = 1;
            while (set.contains(++num)) {
                sum++;
            }
            max = Math.max(sum, max);
        }
    }
    return max;
}