散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
关于散列表更加详细可以看这里散列及散列函数
下面我们通过几个leetcode上的题目加深对散列的理解和使用
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1] 暴力解法
暴力双循环找出符合target - nums[i] = nums[j]条件的 i和j
/**
* 暴力解
* 【O(n^2)】
* @param nums
* @param target
* @return
*/
public int[] twoSum1(int[] nums, int target) {
for(int i = 0; i < nums.length;i++){
for(int j = i+1; j < nums.length;j++){
if(target-nums[j]==nums[i]){
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("不存在这两个数");
} 基于散列解法
因为他要求返回的是索引，且相加两数不是同一个数，所以可以使用一个hashMap将nums中每一个数的数值和对应的索引存到散列表中，数值作为key，索引作为value，遍历哈希表找出符合条件且索引不同的数即可
/**
* 一次哈希表
* O(n)
* @param nums
* @param target
* @return
*/
public int[] twoSum3(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0;i<nums.length;i++){
int k = target - nums[i];
if(map.containsKey(k) && map.get(k) != i){
return new int[]{map.get(k) , i };
}
map.put(nums[i],i);
}
throw new IllegalArgumentException("不存在这两个数");
} 去重问题
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
输入: [1,2,3,1]
输出: true
输入: [1,2,3,4]
输出: false 基于hashSet
关于去重问题其实有更方便的做法就是使用set，set是不包含重复元素的嘛，比较使用set前后的长度差，不相等则有重复值
/**
* 基于set
* 去重后判断前后长度是否一致
* @param nums
* @return
*/
public boolean containsDuplicate2(int[] nums) {
Set<Integer> set = new HashSet<>();
int len = nums.length;
for(int i : nums){
set.add(i);
}
return set.size() != len;
} 基于hashMap
如果我们使用的散列表，在存放元素时出现同一个元素映射到散列表的一个位置，就是属于散列冲突问题，那么当出现冲突时，就是出现重复元素的时候
/**
* 基于hashmap
* @param nums
* @return
*/
public boolean containsDuplicate(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i<nums.length;i++){
if(map.containsKey(nums[i])){
return true;
}
map.put(nums[i],i);
}
return false;
} 滑动窗口问题
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，
并且 i 和 j 的差的绝对值最大为 k。
输入: nums = [1,2,3,1], k = 3
输出: true
输入: nums = [1,2,3,1,2,3], k = 2
输出: false 其实这是一类跟去重问题很相似的问题，但是他要求的是在窗口内去重，或者在窗口内找出符合条件的元素
暴力解
/**
* 暴力解，维护一个长度是k的滑动窗口
* @param nums
* @param k
* @return
*/
public boolean containsNearbyDuplicate(int[] nums, int k) {
for(int i = 0;i < nums.length;i++){
//相当于 j --- 相隔k --- i
for(int j = Math.max(i - k,0);j < i;j++){
if(nums[j] == nums[i]){
return true;
}
}
}
return false;
} 基于hashMap
/**
* hashmap
*/
public boolean containsNearbyDuplicate3(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++){
// i 一定大于 map.get(nums[i])
if(map.containsKey(nums[i]) && i - map.get(nums[i]) <= k){
return true;
}
map.put(nums[i],i);
}
return false;
} 两数组交集问题
基于set
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4] 输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
/**
* 暴力解法（很低效）
* @param nums1
* @param nums2
* @return
*/
public int[] intersection(int[] nums1, int[] nums2) {
// 1.去重
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for(int i : nums1){
set1.add(i);
}
for(int i : nums2){
set2.add(i);
}
ArrayList<Integer> list = new ArrayList<>();
// 2.探寻
for(int i : set1){
for(int j : set2){
if(i == j){
list.add(i);
}
}
}
int[] result = new int[list.size()];
for(int i = 0;i<list.size();i++){
result[i] = list.get(i);
}
return result;
} 使用内置函数
/**
* 使用内置函数
* @param nums1
* @param nums2
* @return
*/
public int[] intersection1(int[] nums1, int[] nums2) {
// 1.去重
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for(int i : nums1){
set1.add(i);
}
for(int i : nums2){
set2.add(i);
}
ArrayList<Integer> list = new ArrayList<>();
//取交集
set1.retainAll(set2);
for(int i : set1){
list.add(i);
}
int[] result = new int[list.size()];
for(int i = 0;i<list.size();i++){
result[i] = list.get(i);
}
return result;
} 基于map
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9] 说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
/**
* 使用hashMap
* @param nums1
* @param nums2
* @return
*/
public int[] intersect(int[] nums1, int[] nums2) {
//统计重复次数
int k = 0;
Map<Integer,Integer> map = new HashMap<>();
//将nums数值和出现的次数存入map中
for(int i = 0;i<nums1.length;i++){
if(map.containsKey(nums1[i])){
map.put(nums1[i],map.get(nums1[i]) + 1);
}else{
map.put(nums1[i],1);
}
}
//找出重复数，存到list，并减少相应的重复次数
List<Integer> list = new LinkedList<>();
for(int j = 0;j<nums2.length;j++){
if(map.containsKey(nums2[j]) && map.get(nums2[j]) > 0){
list.add(nums2[j]);
map.put(nums2[j],map.get(nums2[j])-1);
}
}
//最后，将list中的值放入数组中
int count = list.size();
int[] aux = new int[count];
for(int i = 0; i < count; i++){
aux[i] = ((LinkedList<Integer>) list).poll();
}
return aux;
} ![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)