1. Two Sum & Hash
题目
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
if(nums == null || nums.length <= 1) return res;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++){
int val = target - nums[i];
if(map.containsKey(val) && map.get(val) != i){
res[0] = i;
res[1] = map.get(val);
return res;
}else map.put(nums[i], i);
}
return res;
}
}
数据结构(哈希表Hash)
1.基础
定义:根据关键码(Key)去寻找值(Value)的数据映射。
查询步骤:1. 用散列函数将被查找的键转换为数组的一个索引。2. 再解决碰撞冲突(collision)
2.散列方法
整数:除留余数法(modular hashing),选择大小为素数M(使用素数散列值的分布会更好)的数组,对于任意正整数k,计算k除以M的余数。
浮点数:将键表示为二进制数然后再使用除留余数法(Java使用的方法)
字符串:
//字符串的散列函数
int hash = 0;
for (int i = 0; i < s.length; i++){
hash = (R * hash + s.charAt(i)) % M //charAt()能返回一个char值,即一个16位整数
}
组合键:如果键的类型含有多个整型变量,我们可以和String类型一样将他们混合起来。例如查询Date int hash = (((day * R + month) % M) * R + year) % M
自定义的hashCode方法:在Java中,所有的数据类型都继承了hashCode()方法,因此可以将对象中每个变量的hashCode()返回值转化为32位整数并计算得到散列值
public class Transaction{
private final String who;
private final Date when;
private final double amount;
public int hashCode(){
int hash = 17;
hash = 31 * hash + who.hashCode();
hash = 31 * hash + when.hashCode();
hash = 31 * hash + ((Double) amount).hashCode();
return hash;
}
}
注意:每一种数据的hashCode()必须和equals()一致。需注意,如果两个对象的hashCode()的返回值相同,这两个对象也有可能不同,还需要用equals()进行判断。所以在为自定义的数据类型定义散列函数时,需同时重写hashCode()和equals()
软缓存:如果散列值的计算很耗时,那么可以将每个键的散列值缓存起来。即第一次调用hashCode()时计算对象的散列值,并使用一个hash变量保存其值,之后对hashCode()的调用直接返回hash变量的值。Java的String对象就使用了这种方法来减少计算量
总结:要为一个数据类型实现一个优秀的散列方法需要满足:1. 一致性(等价的键必然产生相等的散列值) 2.高效性(计算简便) 3.均匀性(均匀的散列所有值)
3.解决碰撞的方法
拉链法(separate chaining):将大小为M的数组中的每个元素指向一条链表,链表中的每个结点都存储了散列值为该元素的索引的键值对。
基本思想:选择足够大的M,使得所有链表都尽可能短以保证高效的查找。
删除操作:先用散列值找到含有该键的对象,然后调用该对象的delete()方法
开放地址散列表(open-addressing):用大小为M的数组保存N个键值对(M>N),即依靠数组中的空位解决碰撞冲突。其中线性探测法为最简单的开放地址散列表
基本思想:与其将内存用作链表,不如将他们用做散列表的空元素
线性探测法(linear probing):当发生碰撞时,我们直接检查散列表中的下一个位置。这样线性探测可能产生三种结果:命中(键相同)、未命中(没有键)、继续查找(键不同)。
步骤:用散列函数找到键在数组中的索引,检查其中的键和被查找的键是否相同。如果不同则继续查找(将索引增大,到达数组结尾时折回数组的开头),直到找到该键或者遇到一个空元素
键蔟:元素在插入数组后聚集成的一组连续条目
删除操作:将蔟中被删除键的右侧所有键重新插入散列表。不能直接将该键所在的位置设为null,这会使得在此位置之后的元素无法被查找。
4.分析
性能分析:在没有冲突的情况下查找时间复杂度仅为O(1)。平均性能依赖于冲突的处理方式和散列表的使用率(填装因子),
使用场景:对查找性能要求高,数据元素之间无逻辑关系要求的情况
5.Java HashMap
HashMap基于哈希表实现,其内部通过单链表解决冲突问题。HashMap是非线程安全的,一般用于单线程环境下,多线程环境下可以采用concurrent并发包下的concurrentHashMap(Java 5以上)。
HashMap存数据过程: HashMap内部维护了一个存储数据的Entry数组,每一个Entry本质上是一个单向链表。当准备添加一个key-value对时,首先通过hash(key)方法计算hash值,然后通过indexFor(hash,length)求该key-value对的存储位置,计算方法是先用hash&0x7FFFFFFF屏蔽符号位后,再对length取模,这就保证每一个key-value对都能存入HashMap中,当计算出的位置相同时,由于存入位置是一个链表,则把这个key-value对插入链表头。
HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。
HashMap具体介绍
API
函数名 | 描述 | 函数名 | 描述 |
---|---|---|---|
size() | Map大小 | isEmpty() | Map是否为空 |
get(key) | 返回key对应的value | containsKey(key) | Map中是否包含key |
put(key, value) | 把键值对放入Map中 | putAll(map) | 复制map中的所有键值对到Map中 |
remove(key) | 将key移出Map | clear() | 将Map清空 |
containsValue(value) | 是否含有value | keySet() | 返回一个包含所有key的Set |
values() | 返回一个包含所有value的Collection | clone() | 返回一个Map的浅拷贝 |
2019.3.26创建:完成