【一起来学Java数据结构】——哈希表
文章目录
hashMap的实现
在jvm内部中 ，hashMap是使用数组加链表的方式来实现的，也叫做哈希桶
hashmap的结构
下面是它内部的成员变量
static class Node{
public int key;
public int val;
public Node nextNode;
public Node(int key,int val) {
this.key=key;
this.val=val;
}
}
public Node[] nodes;
public int usedsize;
public static final double DEFAULT_LOAD_FACTOR=0.75;//负载因子
hashmap的插入元素
在这之前，我们一定要明白一件事情。当我们在hashMap中插入的key是一个自定义类型的时候，在该自定义类型内部一定要重写equals和hashcode函数。
hashcode是判断key对应的整数值
equals是判断在同一个hashcode下的元素是否相同。
所以，hashcode相同的，equals不一定相同。equals相同，hashcode一定相同。
class Person{
public String name;
public int ID;
@Override
public int hashCode() {
return Objects.hash(ID, name);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
return ID == other.ID && Objects.equals(name, other.name);
}
}
下面是具体的插入过程：
- 先计算key的hashcode值，并找到应放入的下标
- 在查看在该下标中是否已经存在该值
- 如果存在了，就更新该值
- 如果没有存在就使用头插或尾插来插入
- 计算此时的负载因子，看是否超过指定的值
- 如果超过了就扩容
//插入元素
public void put(K key,V val) {
int hash=key.hashCode();
//先找到相应的下标
int index=hash%this.nodes.length;
//看该下标下是否已经有了该值
//有了该值，就更新,插入操作就已经完成
Node curNode=this.nodes[index];
while(curNode!=null) {
if(curNode.equals(key)) {
curNode.val=val;
return;
}
curNode=curNode.nextNode;
}
//如果没有找到该值的话，就头插
Node node=new Node(key, val);
node.nextNode=this.nodes[index];
this.nodes[index]=node;
this.usedsize++;
//插入之后计算一下负载因子:如果大于就增加数组的长度并重新分配空间
if(loadFactor()>=DEFAULT_LOAD_FACTOR)
resize();//进行扩容
}
private double loadFactor() {
return 1.0*this.usedsize/this.nodes.length;
}
下面来介绍一下扩容函数：
-
将新的数组的长度变为现数组长度的两倍。
-
遍历老数组，将老数组上面的值全部更新到新数组中去
-
将新数组赋予老数组
private void resize() {
Node[] newNodes=new Node[this.nodes.length*2];
for(Node node:this.nodes) {
Node curNode=node;
while(curNode!=null){
//先计算出来新的坐标
int hash=curNode.hashCode();
int newIndex=hash%newNodes.length;
//记录一下该节点后面的节点
Node tmpNode=curNode.nextNode;
//头插法
curNode.nextNode=newNodes[newIndex];
newNodes[newIndex]=curNode;
//更新curNode节点
curNode=tmpNode;
}
}
//最后，让nodes等于我们新扩容的newNodes
this.nodes=newNodes;
}
hashMap的get函数
该函数十分简单，就是遍历一下hashMap看是否可以找到该值就可以。
public V get(K key) {
for(Node node:this.nodes) {
Node curNode=node;
while(curNode!=null) {
if(curNode.equals(key))
return (V)curNode.val;
curNode=curNode.nextNode;
}
}
return null;
}
总体代码
import java.util.Objects;
class Person{
public String name;
public int ID;
@Override
public int hashCode() {
return Objects.hash(ID, name);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
return ID == other.ID && Objects.equals(name, other.name);
}
}
public class HashBuck2<K,V> {
static class Node<K,V>{
public K key;
public V val;
public Node nextNode;
public Node(K key,V val) {
this.key=key;
this.val=val;
}
}
public Node<K,V>[] nodes=(Node<K,V>[])new Node[10];
public int usedsize;
public static final double DEFAULT_LOAD_FACTOR=0.7;
//插入元素
public void put(K key,V val) {
int hash=key.hashCode();
//先找到相应的下标
int index=hash%this.nodes.length;
//看该下标下是否已经有了该值
//有了该值，就更新,插入操作就已经完成
Node curNode=this.nodes[index];
while(curNode!=null) {
if(curNode.key.equals(key)) {
curNode.val=val;
return;
}
curNode=curNode.nextNode;
}
//如果没有找到该值的话，就头插
Node node=new Node(key, val);
node.nextNode=this.nodes[index];
this.nodes[index]=node;
this.usedsize++;
//插入之后计算一下负载因子:如果大于就增加数组的长度并重新分配空间
if(loadFactor()>=DEFAULT_LOAD_FACTOR)
resize();//进行扩容
}
private double loadFactor() {
return 1.0*this.usedsize/this.nodes.length;
}
public V get(K key) {
for(Node node:this.nodes) {
Node curNode=node;
while(curNode!=null) {
if(curNode.key.equals(key))
return (V)curNode.val;
curNode=curNode.nextNode;
}
}
return null;
}
private void resize() {
Node[] newNodes=new Node[this.nodes.length*2];
for(Node node:this.nodes) {
Node curNode=node;
while(curNode!=null){
//先计算出来新的坐标
int hash=curNode.hashCode();
int newIndex=hash%newNodes.length;
//记录一下该节点后面的节点
Node tmpNode=curNode.nextNode;
//头插法
curNode.nextNode=newNodes[newIndex];
newNodes[newIndex]=curNode;
//更新curNode节点
curNode=tmpNode;
}
}
//最后，让nodes等于我们新扩容的newNodes
this.nodes=newNodes;
}
}
hashMap的源码
声明的变量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 最开始的容量必须是2的幂数，其实也是有道理的，因为左移都是以2的倍数为单位的
static final int MAXIMUM_CAPACITY = 1 << 30;//最大的容量只可以是2^30
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;//当链表的长度超过8且总容量大于64的时候就树化
static final int UNTREEIFY_THRESHOLD = 6;//从红黑树转到链表的条件是红黑树的节点的个数小于6个的时候
hashMap的构造函数
构造函数1
具有初始化容量和负载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
构造函数2
具有初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
构造函数3
无参数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
hash函数
第一步：先是调用hashCode函数得到h值。这是一个32位的数，但是我们的数组只是有16位，太大了。所以在第二步进行一些处理
第二步：将h和h>>>16进行异或，这样就增加了低位的随机性，使得数据不会聚集在一起。
第三步：就是hash值和数组长度取模的过程。因为数组长度总是2的幂数，且与的效率比取余的效率高，所以就使用（n-1）和hansh值相与
put函数
这里我们需要有一个小问题，就是什么时候进行数组的开辟。
事实上，在我们进行构造函数的时候，并没有对数组进行开辟。
通过看put函数的源码，我们可以看到：
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
只有在插入第一个元素的时候，才会有数组的开辟
hashMap的面试题
-
如果new HashMap(19),那么hashMap的数组开辟的空间是多大？
开辟的空间是最接近19且大于19的2的幂数，也就是25
-
hashMap如何扩容，怎么扩容？
当小于负载因子的时候进行扩容，以两倍的方式进行扩容
-
查找成功和查找不成功的平均查找长度
查找成功的长度：整个的比较次数相加/关键字的个数
查找不成功的长度：对于每一个元素都要进行比较。对于没有值的元素就是1，有值的就是要看出现经过多少次操作出现空位。
然后再除以整个数组的长度。
? 4.待解决的问题
? 