1、哈希表
- 散列表，是根据关键码值（Key）进行访问的数据结构，也就是说，通过将Key映射到表中一个位置来获取记录，加快查找的速度，这个映射函数叫做撒案列函数，存放记录的结构称之为散列表
- 寻址容易，删除插入也容易的数据结构
通常以下几种方式构造哈希函数 - 1）直接定址法 key address(key) = a*key + b
- 2）平方取中法 key 108 109 110 = 108^2 109^2 110^2
- 3）折叠法 key -> 拆分为几部分 区域号-书架号-图书编号
- 4）除留取余法 key -> hash表的最大长度m 取不大于m的质数 key%质数
解决冲突 - 1）开放地址法 12 13 25 23 hash表的长度14 hash函数key%13
- 2）链地址法
2、HashMap的使用 - HashMap基于哈希表(散列表)非同步实现的，哈希表对应的接口是Map接口（非线程安全）
- jdk1.8之前，HashMap都是采用数组+链表实现的，即使用链地址法处理哈希冲突，不同的key值可能得到同样的散列码，统一hash值的节点都存储在一个链表中的，但是当链表中的元素越来越多的时候，通过key去查找的效率反而从O(1)->O(N)。jdk1.8中，HashMap采用数组+链表+红黑树的结构实现，当前链表的长度超过阀值8，将链表转换为红黑树，红黑树中的元素个数小于6，将红黑树再转换为链表
自定义HashMap，hash算法直接使用HashMap中的hash算法，解决哈希冲突
-
采用链地址法，即链表+数组实现，包括方法有put(K key, V value), get(K key),
-
remove(K key)等方法
-
hashCode方法是将引用类型的内存地址转换为一个32位的整型返回，所以存在一定的限制，导致两个不同对象有可能hashCode也会相等，这样的话比较了hash值还需要比较引用，才能够保证两个对象完全相等。
HashMap迭代器实现
- 1）哈希表中数据分布是不连续的，在迭代器初始化的过程中必须先跳转到第一个非空数据节点
- 2）当迭代器的下标到达当前桶的链表末尾时，迭代器下标跳转到下一个非空桶的第一个数据节点
class MyHashMap<K,V>{
private Node<K, V>[] table;
private int size;
class Node<K,V>{
protected K key;
protected V value;
protected int hash;
protected Node<K, V> next;
public Node(K key, V value, int hash) {
this.key = key;
this.value = value;
this.hash = hash;
}
}
public MyHashMap(int capacity){
table = new Node[capacity];
}
public Iterator<Node<K, V>> iterator(){
return new Itr();
}
class Itr implements Iterator<Node<K, V>>{
private int currentIndex;//当前桶的位置
private Node<K, V> nextNode;//返回的下一个数据节点
private Node<K, V> currentNode; //上一次next返回的数据节点
public Itr(){
if(MyHashMap.this.isEmpty()){
return;
}
for(int i=0; i < table.length; i++){
currentIndex = i;
Node<K, V> firstNode = table[i];
if(firstNode != null){
nextNode = firstNode;
return;
}
}
}
@Override
public boolean hasNext() {
return nextNode != null;
}
@Override
public Node<K, V> next() {
//返回下一个数据节点
currentNode = nextNode;
//nextNode指向自己的next
nextNode = nextNode.next;
if(nextNode == null){
//说明当前桶的链表已经遍历完毕
//寻找下一个非空的桶
for(int i=currentIndex+1; i<MyHashMap.this.table.length; i++){
//设置当前桶位置
currentIndex = i;
Node<K,V> firstNode = MyHashMap.this.table[currentIndex];
if(firstNode != null){
nextNode = firstNode;
break;
}
}
//nextNode保存的就是下一个非空的数据节点
}
return currentNode;
}
@Override
public void remove() {
if(currentNode == null){
return;
}
K currentKey = currentNode.key;
MyHashMap.this.remove(currentKey);
currentNode = null;
}
}
public void resize(){
//扩容桶table
Node<K, V>[] newTable = new Node[table.length * 2];
for(int i=0; i<table.length; i++){
//将oldTable中每一个位置映射到newTable中
rehash(i, newTable);
}
this.table = newTable;
}
public void rehash(int index, Node<K,V>[] newTable){
Node<K, V> currentNode = table[index];
if(currentNode == null){
return;
}
Node<K, V> lowListHead = null; //低位的头
Node<K, V> lowListTail = null; //低位的尾
Node<K, V> highListHead = null; //高位的头
Node<K, V> highListTail = null; //高位的尾
//currentNode表示oleTable下index位置中当前节点
while(currentNode != null){
//当前节点在newTable中的位置
int newIndex = newTable.length-1 & hash(currentNode.key);
if(newIndex == index){
//映射到原先下标处
if(lowListHead == null){
lowListHead = currentNode;
lowListTail = currentNode;
}else{
lowListTail.next = currentNode;
lowListTail = lowListTail.next;
}
}else{
//newIndex与index不等，映射到高位下标处
if(highListHead == null){
highListHead = currentNode;
highListTail = currentNode;
}else{
highListTail.next = currentNode;
highListTail = lowListTail.next;
}
}
currentNode = currentNode.next;
}
//将lowList head->tail之前的节点链接到index位置
if(lowListTail != null){
newTable[index] = lowListHead;
lowListHead.next = null;
}
//将highList head->tail之前的节点链接到index+table.length位置
if(highListTail != null){
newTable[index+this.table.length] = highListHead;
highListHead.next = null;
}
}
public int hash(Object key) {
int h;
return (h = key.hashCode()) ^ (h >>> 16);
}
public void put(K key, V value){
//确定所要添加元素的位置
int hash = hash(key);//散列码
int index = table.length-1 & hash;//确定的位置
//newNode -》table[index] == null || key在map不存在
//table[index]已经存在数据
//table[index]不存在数据
Node<K, V> firstNode = table[index];//得到该位置的第一个节点
if(firstNode == null){
table[index] = new Node(key, value, hash);
size++;
}else{
//第一种情况 key已经存在 考虑新值覆盖旧值
//第二种情况 key不存在 封装一个新的node尾插法插入链表
if(firstNode.key.equals(key)){
firstNode.value = value; //新值替换旧值
}else{
Node<K,V> tmp = firstNode;
while(tmp.next != null && !tmp.key.equals(key)){
tmp = tmp.next;
}
if(tmp.next == null){
if(tmp.key.equals(key)){
tmp.value = value; //新值替换旧值
}else{
tmp.next = new Node(key, value, hash);
size++;
}
}else{
tmp.value = value;
}
}
}
}
public boolean remove(K key){
int hash = hash(key);
int index = table.length-1 & hash;
Node<K, V> firstNode = table[index];
if(firstNode == null){
return false;
}else{
if(firstNode.next == null){
if(firstNode.key.equals(key) && firstNode.hash == hash){
//为什么判断key是否相等的同时还需要判断散列码
table[index] = null;
return true;
}
}
Node<K,V> tmpPrev = firstNode;
Node<K, V> tmp = firstNode.next;
while(tmp.next != null){
if(tmp.key.equals(key) && tmp.hash == hash){
//tmp之前节点的next指向tmp.next
tmpPrev.next = tmp.next;
size--;
}else{
tmpPrev = tmp;
tmp = tmp.next;
}
}
}
return false;
}
public Node<K,V> get(K key){
//获取对应key所在数组的index
int hash = hash(key);//散列码
int index = table.length - 1 & hash; //定位key记录所在的位置
Node<K, V> firstNode = table[index];
if (firstNode == null) {
return null;
}
if (hash == firstNode.hash && key == firstNode.key) {
return firstNode;
} else {
//遍历链表
Node<K, V> currentNode = firstNode.next;
while (currentNode != null) {
if (currentNode.hash == hash && currentNode.key == key) {
return currentNode;
}
currentNode = currentNode.next;
}
}
return null;
}
public boolean isEmpty(){
return size == 0;
}
}
public class TestDemo11 {
public static void main(String[] args) {
}
}
java当中四种引用
- 强引用
- 通过new出来对象所关联的引用称之为强引用，只要强引用存在，当前对象不会被回收
- 软引用
- 通过SoftReference类实现，在系统内存即将要溢出的时候，才会回收软引用对象
- 弱引用
- 通过WeakReference实现，只要发生GC，被弱引用关联的对象就会被回收掉
- 虚引用
- 通过PhantomReference实现，无法通过虚引用获取对象实例，唯一作用就是在这个对象被回收时，能够收到一个通知
本文地址：https://blog.csdn.net/weixin_43751188/article/details/109626866
