目录
哈希表
避免哈希冲突
设计哈希函数
调节负载因子
解决哈希冲突
开放地址法
线性探测法
二次探测法
链地址法
Map接口
HashMap集合
HashMap的底层实现
常用方法
put方法---添加元素
get方法--根据key值得到value值
?遍历
?LinkedHashMap集合:保证元素的输入顺序
?TreeMap集合
hashtree和hashmap的区别
1、输出的有序性
?2.对null的要求
?3、性能分析
我们查找一个数据时,遍历元素的查找时间复杂度O(n),二分查找的时间复杂度O(log2N)……那有没有可能查找的时间复杂度在O(1)呢?这就是哈希表
哈希表
根据某一种映射关系,将元素存储在某一个特定位置,查找元素时,根据这个映射关系得到存储位置---》这就是哈希表
这个映射关系就是哈希函数
但是有一个问题,如果我还有一个元素是33呢,根据上图的映射关系,33%11==0,应该放在0下标,但是0下标已经有一个元素11了,33又放到哪里?这种产生的冲突就是哈希冲突
那么如何避免,如何解决哈希冲突呢?
避免哈希冲突
设计哈希函数
设计更好的哈希函数,可以尽量避免哈希冲突
好的哈希函数满足的条件:
- 哈希函数的定义域必须包括了所有的数据。如果哈希表长度是m,那么所有的数据使用哈希函数得到的下标都必须在0~m-1之间
- 元素按照哈希函数得到的存储位置尽可能的均匀
- 哈希函数尽量简单
常用的哈希函数设计方法:
1、直接定址法:hash(key)=A*key+b
线性函数:y=kx+b---》均匀的分布在线性函数附近
2、除留余数法:hash(key)=key%a---得到的下标位置[0~a-1]
调节负载因子
负载因子=存入哈希表的元素个数/哈希表的长度
如果负载因子过大,冲突的可能性越大,那么就可以来增大哈希表的长度来减少发生冲突的可能
解决哈希冲突
冲突无法完全避免,我们要想办法解决冲突
开放地址法
只要数组有空元素,找到空元素位置存放冲突元素
线性探测法
?H=(hash(key)+d)%m
二次探测法
H=(hash(key)±a^2)%m
链地址法
数组+链表
??jdk1.8开始,?当链表长度超过8且数组长度超过64,这时候链表会转为红黑树(查找非常高效的树)
通常情况下,哈希表插入和查找的时间复杂度O(1)
Map接口
一个人的身份证号唯一对应了这个人,这种具有对应关系的数据的存储就需要Map接口
Map接口是一种双列集合,每个元素都包含一个键对象Key和值对象Value,键和值之间存在着某一种对应关系,称为映射
Map接口中的映射关系是一对一的,一个键对象对应着唯一的值对象,Key和Value都可以是任意的数据类型,并且键对象Key不允许重复,这样通过key可以找到唯一指定的value(key---value模型)
HashMap集合
HashMap集合是Map接口的实现类,用于存储键值之间的映射关系,键不能重复,且集合元素是无序的
HashMap的底层实现
hashmap的底层是一个哈希表,这个哈希表使用链表解决冲突(JDK1.8后,当链表长度大于8且数组长度>64,链表变成红黑树)
常用方法
put方法---添加元素
?如何添加元素:?
1、根据提供的key(键值)得到对应的hash值
2、根据对应的hash值,找到哈希表数组的相对应存储位置
3、判断这个数组位置是不是有结点,没有结点直接插入结点;数组位置有结点,判断链表中是否有结点的key和插入结点的key相同,相同意味着value值要更新;如果不存在一个结点的key和插入结点的key相同,那么意味着要在链表插入结点(jdk1.8之后使用尾插法)
4、插入一个元素,就要计算负载因子,负载因子越大,产生冲突的可能性就越大,可以通过增大数组长度来减小负载因子。(数组不是单纯的扩容,数组长度改变,哈希函数改变,所有元素都需要重新哈希入新的数组)
简单的模拟实现:
public class Myhashmap {
class Node {
int key;
int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"key=" + key +
", value=" + value +
"}";
}
}
private int count = 0;//记录存入的数据个数
private final float loadFactor = 0.75f;//hashmap默认的装载因子是0.75f
Node[] table = new Node[10];//table存放的是new Node这个实例化对象的引用,现在存放是null
/**
* 根据key插入元素value
*/
public void put(int key, int value) {
//第一步,设计hash函数,得到hash值
int hash = key % table.length;
//第二步:插入结点的key已经存在
Node cur = table[hash];
while (cur != null) {
if (cur.key == key) {
cur.value = value;
return;
}
cur = cur.next;
}
//第三步:插入结点的key不存在(jdk1.8后使用尾插法)
cur = table[hash];
Node newode = new Node(key, value);
if (cur == null) {
table[hash] = newode;
count++;
loadFactor(key, value);
return;
}
while (cur.next != null) {
cur = cur.next;
}
cur.next = newode;
count++;
//第四步,计算装载因子(存入的元素个数除以数组长度)
loadFactor(key, value);
}
private void loadFactor(int key, int value) {
if (count * 1.0f / table.length > loadFactor) {//数组扩容,hashmap数组2倍扩容
reseize();
}
}
private void reseize() {
Node[] newtable = new Node[table.length * 2];
//遍历之前的数组,例如hash(4)存储的key=14就要重新hash到新数组的hash(14)位置
for (int i = 0; i < table.length; i++) {
Node cur = table[i];
Node newnode;
while (cur != null) {//链表的每一个元素全部重新哈希(jdk1.8后使用尾插法,其实头插简单)
int hash = cur.key % newtable.length;
newnode = newtable[hash];
Node curNext = cur.next;
cur.next = null;
if (newnode == null) {
newtable[hash] = cur;
cur = curNext;
continue;
}
while (newnode.next != null) {
newnode = newnode.next;
}
newnode.next = cur;
cur = curNext;
}
}
table = newtable;
}
public void print() {
for (int i = 0; i < table.length; i++) {
Node node = table[i];
while (node != null) {
System.out.println(node);
node = node.next;
}
}
}
}
hashmap的源码设置:
数组长度默认16,二倍扩容,负载因子是0.75,当链表长度超过8并且数组长度超过64的时候,链表转化为红黑树
get方法--根据key值得到value值
模拟实现:
public Node get(int key) {
for (int i = 0; i < table.length; i++) {
Node node = table[i];
while (node != null) {
if(node.key==key)
return node;
node = node.next;
}
}
return null;
}
?hashmap的泛型类实现:
class Person{
int ID;
public Person(int ID) {
this.ID = ID;
}
@Override
public String toString() {
return "Person{" +
"ID=" + ID +
'}';
}
}
public class hash {
public static void main(String[] args) {
Person person=new Person(123);
Person person1=new Person(123);
System.out.println(person.hashCode());
System.out.println(person1.hashCode());
}
}
hashCode方法可以将引用类型转化为整数,但是我们想让身份证后三位相同的人,产生相同的hash值,发现做不到,产生的整数值是不相同的
?但是,我们重写equals and?hashCode方法之后:
?就会产生相同的整数
?为什么要同时重写equals()和?hashCode()方法呢?
equals()用于比较是否相等,hashCode()用于生成整数
hashCode()相同,equal()不一定相同
equals()相同,hashCode()一定相同
public class Myhashmap<K,V> {
class Node <K,V>{
K key;
V value;
Node <K,V>next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"key=" + key +
", value=" + value +
"}";
}
}
private int count = 0;//记录存入的数据个数
private final float loadFactor = 0.75f;//hashmap默认的装载因子是0.75f
Node <K,V>[] table = new Node [10];//table存放的是new Node这个实例化对象的引用,现在存放是null
/**
* 根据key插入元素value
*/
public void put(K key, V value) {
//第一步,设计hash函数,得到hash值
int hash = key.hashCode() % table.length;
//第二步:插入结点的key已经存在
Node <K,V>cur = table[hash];
while (cur != null) {
if (cur.key .equals(key) ) {
cur.value = value;
return;
}
cur = cur.next;
}
//第三步:插入结点的key不存在(jdk1.8后使用尾插法)
cur = table[hash];
Node<K,V> newode = new Node<K,V>(key, value);
if (cur == null) {
table[hash] = newode;
count++;
loadFactor(key, value);
return;
}
while (cur.next != null) {
cur = cur.next;
}
cur.next = newode;
count++;
//第四步,计算装载因子(存入的元素个数除以数组长度)
loadFactor(key, value);
}
private void loadFactor(K key, V value) {
if (count * 1.0f / table.length > loadFactor) {//数组扩容,hashmap数组2倍扩容
reseize();
}
}
private void reseize() {
Node<K,V>[] newtable = new Node[table.length * 2];
//遍历之前的数组,例如hash(4)存储的key=14就要重新hash到新数组的hash(14)位置
for (int i = 0; i < table.length; i++) {
Node<K,V> cur = table[i];
Node<K,V> newnode;
while (cur != null) {//链表的每一个元素全部重新哈希(jdk1.8后使用尾插法,其实头插简单)
int hash = cur.key.hashCode() % newtable.length;
newnode = newtable[hash];
Node<K,V> curNext = cur.next;
cur.next = null;
if (newnode == null) {
newtable[hash] = cur;
cur = curNext;
continue;
}
while (newnode.next != null) {
newnode = newnode.next;
}
newnode.next = cur;
cur = curNext;
}
}
table = newtable;
}
public void print() {
for (int i = 0; i < table.length; i++) {
Node<K,V> node = table[i];
while (node != null) {
System.out.println(node);
node = node.next;
}
}
}
public Node<K,V> get(int key) {
for (int i = 0; i < table.length; i++) {
Node<K,V> node = table[i];
while (node != null) {
if(node.key.equals(key))
return node;
node = node.next;
}
}
return null;
}
}
?遍历
1、迭代器
public static void main(String[] args) {
Map <String,Integer> map=new HashMap<>();
map.put("123",1);
map.put("145",9);
Set<String>set=map.keySet();//获取key值的集合
Iterator it=set.iterator();
while(it.hasNext()){
Object key=it.next();//获取key
Object value=map.get(key);//获取key对应的value
System.out.println(key+" "+value);
}
}
2、
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("123", 1);
map.put("145", 9);
Set set = map.entrySet();//将所有的键值对打包到一起,成为Set集合返回
Iterator it=set.iterator();
while(it.hasNext()){
Map.Entry ret=(Map.Entry)(it.next());//将Iterator对象的其中一个转化为 Map.Entry<K,V>
Object key=ret.getKey();
Object value=ret.getValue();
System.out.println(key+" "+value);
}
}
3、for-each
Lambda表达式的函数式接口BIConsumer
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("123", 1);
map.put("145", 9);
map.forEach((key,value)-> System.out.println(key+" "+value));
}
?LinkedHashMap集合:保证元素的输入顺序
使用hashmap集合无法保证集合元素的存入和取出顺序
LinkedHashMap是hashmap的子类,内设双向链表来维护元素内部之间的关系,保证元素的输出顺序和存入顺序一致
public static void main(String[] args) {
Map<Integer, Integer> map = new HashMap<>();
map.put(1, 9);
map.put(3,0);
map.put(2, 1);
System.out.println(map);
Map<Integer, Integer> map1 = new LinkedHashMap<>();
map1.put(1, 9);
map1.put(3,0);
map1.put(2, 1);
System.out.println(map1);
}
?TreeMap集合
底层实现是一个红黑树
??TreeTree会自动对key值进行排序存储(String 类实现了Comparator接口)hashtree适用于key有序的情况下
hashtree和hashmap的区别
1、输出的有序性
hashmap的key值无顺序,hashtree的key有顺序
public static void main(String[] args) {
Map<Integer,String>map=new HashMap<>();
map.put(78,"8");
map.put(0,"8");
map.put(89,"8");
System.out.println(map);
Map<Integer,String>maptree=new TreeMap<>();
maptree.put(78,"8");
maptree.put(0,"8");
maptree.put(89,"8");
System.out.println(maptree);
}
?2.对null的要求
?hashmap可以让key和value都是null
1、key==null&&value==null ---存入键值对(null,null)
2、key==null&&value!=null ---不存入键值对,但是不会抛出异常
3、key!=null&&value==null ---存入键值对(key,null)
hashtree的key不能是null,value可以是null,否则抛出异常
public static void main(String[] args) {
Map<String,Integer> maptree=new TreeMap<>();
maptree.put("hi",null);
System.out.println(maptree);
System.out.println(maptree.size());
}
?3、性能分析
hashmap的底层是链表+数组,查找和插入的时间复杂度都是O(1)
hashtree的底层是红黑树,查找和插入的时间复杂度都是O(log2 N)
|