为什么重写equals还要重写hashcode方法
- Object 的 hashcode 方法是本地方法,也就是用 c 或 c++ 实现的,该方法直接返回对象的内存地址,再转换整数。
- Equals方法规定:
- 两个对象的Hashcode值相等,但是两个对象的内容值不一定相等;---Hash冲突的问题
- 两个对象的值Equals比较相等的情况下,则两个对象的Hashcode值一定相等;
== 比较两个对象的内存地址是否相同、Equals默认的情况下比较两个对象的内存地址
【强制】关于 hashCode 和 equals 的处理,遵循如下规则:
1) 只要覆写 equals,就必须覆写 hashCode。
2) 因为 Set 存储的是不重复的对象,依据 hashCode 和 equals 进行判断,所以 Set 存储的对象必须覆写这两个方法。
3) 如果自定义对象作为 Map 的键,那么必须覆写 hashCode 和 equals。
说明:String 已覆写 hashCode 和 equals 方法,所以我们可以愉快地使用 String 对象作为 key 来使用。
HashMap如何避免内存泄漏问题
自定义对象作为HashMap的key时,一定要去从写hashCode和equals方法。保证对象key不重复创建。
package com.example.awenproject.container;
import java.util.HashMap;
/**
* 演示内存泄漏问题
* -Xmx3M -Xms3M 设置堆内存和栈内存大小
*/
public class HashmapMemoryLeak {
//自定义对象作为hashmap的key
static class HashKey {
private String name;
private String id;
public HashKey(String name, String id) {
this.name = name;
this.id = id;
}
@Override
public int hashCode() {
return name.hashCode();
}
/**
* 不管new多少次,相同的key只会被覆盖,不会继续添加
*
* @param obj
* @return
*/
@Override
public boolean equals(Object obj) {
if (obj instanceof HashKey) {
return name.equals(((HashKey) obj).name) && id.equals(((HashKey) obj).id);
} else {
return false;
}
}
}
public static void main(String[] args) {
HashMap<HashKey, Integer> map = new HashMap<>(1000);
int count = 0;
while (true) {
HashKey p = new HashKey("awen", "991128");
//如果没有从写equals方法 底层默认采用==比较两个对象的内存地址
map.put(p, 1);
count++;
if (count % 1000 == 0) {
//new 多个不同的对象 参数都是相同的内容,但是对象的内存地址是不同的
System.out.println("map size:" + map.size());
System.out.println("运行" + count + "次后,可以内存剩余" + Runtime.getRuntime().freeMemory() / (1024 * 1024) + "MB");
}
//如果不从写hashcode和equals方法,则运行36000次后,可以内存剩余0MB时会报内存溢出---java.lang.OutOfMemoryError: GC overhead limit exceeded
//如果从写hashcode和equals方法,程序运行40000次自动跳出循环
if (count % 40000 == 0) {
break;
}
}
}
}
HashMap与HashTable之间的区别
- HashMap实现不同步,线程不安全。 HashTable线程安全 HashMap中的key-value都是存储在Entry中的。
- 继承不同。 Hashtable 继承 Dictionary 类,而 HashMap 继承 AbstractMap。
- 线程安全。Hashtable中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下,可以直接使用Hashtable,但是要使用HashMap的话就要自己增加同步处理了。
- 是否存放null值。Hashtable 中, key 和 value 都不允许出现 null 值。 在 HashMap 中, null 可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为 null 。
- 当 get() 方法返回 null 值时,即可以表示 HashMap 中没有该键,也可以表示该键所对应的值为 null 。因此,在 HashMap 中不能由 get() 方法来判断HashMap 中是否存在某个键,而应该用 containsKey() 方法来判断。
- hash值。哈希值的使用不同,HashTable直接使用对象的hashCode。而HashMap重新计算hash值
HashMap1.7底层是如何实现的
1、基于ArrayList集合实现方式
优点:不需要考虑hash碰撞的问题
缺点:时间复杂度为O(n),查询效率低
package com.example.awenproject.container;
import java.util.ArrayList;
import java.util.List;
/**
* ArrayList实现HashMap
*
* @param <K>
* @param <V>
*/
public class ArrayListHashMap<K, V> {
//定义Entry存放key-valua值
class Entry<K, V> {
K k;
V v;
public Entry(K k, V v) {
this.k = k;
this.v = v;
}
}
private List<Entry<K, V>> entrys = new ArrayList<>();
/**
* put方法,向list里面存放元素
*
* @param k
* @param v
*/
public void put(K k, V v) {
entrys.add(new Entry<K, V>(k, v));
}
/**
* get方法,通过遍历key值取出元素,时间复杂度为O(n),查询效率低
*
* @param k
* @return
*/
public V get(K k) {
for (Entry entry : entrys) {
if (entry.k.equals(k)) {
return (V) entry.v;
}
}
return null;
}
public static void main(String[] args) {
ArrayListHashMap<Object, String> arrayListHashMap = new ArrayListHashMap<>();
arrayListHashMap.put("a", "a");
arrayListHashMap.put(97, "97");
System.out.println(arrayListHashMap.get("a"));
System.out.println(arrayListHashMap.get(97));
}
}
2、基于数组+链表方式(jdk1.7)
hashMap中key如果没有发生hash碰撞问题,get查询的时间复杂度为O(1)直接根据下标查询。
package com.example.awenproject.container;
public class ExtHashMap<K, V> {
/**
* 数组+链表
* 定义Entry存放key-valua值
*
* @param <K>
* @param <V>
*/
class Entry<K, V> {
K k;
V v;
Entry<K, V> next;
public Entry(K k, V v) {
this.k = k;
this.v = v;
}
}
private Entry[] entrys = new Entry[10000];
/**
* put方法,向list里面存放元素
*
* @param k
* @param v
*/
public void put(K k, V v) {
//判断k值是否为null,为null则存放在数组的第0个位置
int index = k == null ? 0 : k.hashCode() % entrys.length;
//判断key是否产生hash冲突,产生冲突则链表存储
Entry oldEntry = entrys[index];
if (oldEntry == null) {
entrys[index] = new Entry<K, V>(k, v);
} else {
oldEntry.next = new Entry<K, V>(k, v);
}
}
/**
* get方法,
*
* @param k
* @return
*/
public V get(K k) {
//判断k值是否为null,为null则存放在数组的第0个位置
int index = k == null ? 0 : k.hashCode() % entrys.length;
for (Entry oldEntry = entrys[index]; oldEntry != null; oldEntry = oldEntry.next) {
if ((k == null && oldEntry.k == null) || oldEntry.k.equals(k)) {
return (V) oldEntry.v;
}
}
return null;
}
public static void main(String[] args) {
ExtHashMap<Object, String> extHashMap = new ExtHashMap<>();
extHashMap.put("a", "a");
extHashMap.put(97, "97");
extHashMap.put(null, "awennull");
extHashMap.put(null, "awennull2");
System.out.println(extHashMap.get("a"));
System.out.println(extHashMap.get(97));
System.out.println(extHashMap.get(null));
}
}
3、基于数组+链表+红黑树方式(jdk1.8)