## Java之HashMap的实现
基于java.util.Map接口实现的简单版HashMap；
~~~
/**
* HashMap实现
* @Author: mango
* @Date: 2022/5/21 10:53 上午
* @Desc: 数组加链表
*/
public class HashMap<K,V> implements Map<K,V> {
private Node<K,V>[] array;
// 容量
private int capacity;
// 大小
private int size;
// 默认容量
private int DEFAULT_CAPACITY = 8;
// 负载因子
private float LOAD_FACTOR = 0.75f;
public HashMap(){
this.size = 0;
}
// hash函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean containsKey(Object key) {
return getNode(hash(key), (K) key) != null ? true : false;
}
private Node<K,V> getNode(int hash,K key){
int index = hash % capacity;
if(array[index] == null){
return null;
}else{
Node<K,V> node = array[index];
while (node != null && !node.key.equals(key)){
node = node.next;
}
if(node != null){
return node;
}
}
return null;
}
private Node<K,V> getNodeByVal(int hash,V val){
int index = hash % capacity;
if(array[index] == null){
return null;
}else{
Node<K,V> node = array[index];
while (node != null && !node.val.equals(val)){
node = node.next;
}
if(node != null){
return node;
}
}
return null;
}
@Override
public boolean containsValue(Object value) {
return getNodeByVal(hash(value),(V)value) == null ? true : false;
}
@Override
public V get(Object key) {
if(containsKey(key)){
return getNode(hash(key), (K) key).val;
}
return null;
}
// 扩容,缩容
private void resize(int flag){
int oldCapacity = capacity;
Node<K,V>[] oldArray = this.array;
if(flag == 1) {
this.capacity = this.capacity << 1;
}else{
this.capacity = this.capacity >> 1;
}
this.array = new Node[capacity];
this.size = 0;
for(int i=0;i<oldCapacity;i++){
Node<K, V> node = oldArray[i];
if(node != null){
putVal(node.key,node.val);
while (node.next != null){
putVal(node.next.key,node.next.val);
node = node.next;
}
}
}
}
private void resize(){
int m = (int) (capacity * LOAD_FACTOR / 2);
// 超过负载，则扩容
if(size / capacity > LOAD_FACTOR){
resize(1);
System.out.println("扩容");
}
// 低于负载的一半，且缩减后的容量不小于默认容量，则缩容
else if(size < m && m >= (DEFAULT_CAPACITY / 2) ){
resize(0);
System.out.println("缩容");
}
}
@Override
public V put(K key, V value) {
// 如果为空，则先创建默认容量大小的数组
if(array == null){
this.array = new Node[DEFAULT_CAPACITY];
this.capacity = DEFAULT_CAPACITY;
}
// 设置值
putVal(key,value);
// 容量控制
resize();
return value;
}
private void putVal(K key,V value){
int index = hash(key) % capacity;
Node<K,V> node = array[index];
// 如果key已经存在，则替换value的值
if(containsKey(key)){
getNode(hash(key),key).val = value;
return ;
}
// 不存在，则加入
if(node == null){
array[index] = new Node(key,value);
}else{
while (node.next != null){
node = node.next;
}
node.next = new Node(key,value);
}
size++;
}
@Override
public V remove(Object key) {
if(containsKey(key)){
int index = hash(key) % capacity;
if(array[index] != null){
Node<K,V> node = array[index];
if(node.next == null){
array[index] = null;
}else{
while (node.next != null && !node.next.key.equals(key)){
node = node.next;
}
node.next = node.next.next;
}
size--;
// 容量控制
resize();
}
}
return null;
}
@Override
public void putAll(Map m) {
for(Object k : m.keySet()){
K key = (K) k;
putVal(key, (V) m.get(k));
}
}
@Override
public void clear() {
this.size = 0;
this.capacity = 0;
this.array = null;
}
@Override
public Set<K> keySet() {
HashSet set = new HashSet();
for(int i=0;i<capacity;i++){
Node<K, V> node = this.array[i];
if(node != null){
set.add(node.key);
while (node.next != null){
set.add(node.next.key);
node = node.next;
}
}
}
return set;
}
@Override
public Collection values() {
List<V> result = new ArrayList<>();
for(int i=0;i<capacity;i++){
Node<K, V> node = this.array[i];
if(node != null){
result.add(node.val);
while (node.next != null){
result.add(node.next.val);
node = node.next;
}
}
}
return result;
}
@Override
public Set<Entry<K, V>> entrySet() {
HashSet<Entry<K,V>> set = new HashSet();
for(int i=0;i<capacity;i++){
Node<K, V> node = this.array[i];
if(node != null){
set.add(node);
while (node.next != null){
set.add(node.next);
node = node.next;
}
}
}
return set;
}
/**
* 链表节点
*/
final class Node<K,V> implements Entry<K,V>{
public K key;
public V val;
public Node<K,V> next;
public Node(K key, V val) {
this.val = val;
this.key = key;
}
@Override
public String toString() {
return "Node{" +
"key=" + key +
", val=" + val +
", next=" + next +
'}';
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return val;
}
@Override
public V setValue(V value) {
this.val = value;
return value;
}
}
@Override
public String toString() {
return "HashMap{" +
"array=" + Arrays.toString(array) +
", capacity=" + capacity +
", size=" + size +
'}';
}
}
~~~
- Redis来回摩擦
- redis的数据结构SDS和DICT
- redis的持久化和事件模型
- Java
- 从何而来之Java IO
- 发布Jar包到公共Maven仓库
- Java本地方法调用
- 面试突击
- Linux
- Nginx
- SpringBoot
- Springboot集成Actuator和SpringbootAdminServer监控
- SpringCloud
- Spring Cloud初识
- Spring Cloud的5大核心组件
- Spring Cloud的注册中心
- Spring Cloud注册中心之Eureka
- Spring Cloud注册中心之Consul
- Spring Cloud注册中心之Nacos
- Spring Cloud的负载均衡之Ribbon
- Spring Cloud的服务调用之Feign
- Spring Cloud的熔断器
- Spring Cloud熔断器之Hystrix
- Spring Cloud的熔断器监控
- Spring Cloud的网关
- Spring Cloud的网关之Zuul
- Spring Cloud的配置中心
- Spring Cloud配置中心之Config Server
- Spring Cloud Config配置刷新
- Spring Cloud的链路跟踪
- Spring Cloud的链路监控之Sleuth
- Spring Cloud的链路监控之Zipkin
- Spring Cloud集成Admin Server
- Docker
- docker日常基本使用
- docker-machine的基本使用
- Kubernetes
- kubernetes初识
- kubeadm安装k8s集群
- minikube安装k8s集群
- k8s的命令行管理工具
- k8s的web管理工具
- k8s的相关发行版
- k3s初识及安装
- rancher的安装及使用
- RaspberryPi
- 运维
- 域名证书更新
- 腾讯云主机组建内网
- IDEA插件开发
- 第一个IDEA插件hello ide开发
- 千呼万唤始出来的IDEA笔记插件mdNote
- 大刚学算法
- 待整理
- 一些概念和知识点
- 位运算
- 数据结构
- 字符串和数组
- LC242-有效的字母异位词
- 链表
- LC25-K个一组翻转链表
- LC83-删除有序单链表重复的元素
- 栈
- LC20-有效的括号
- 队列
- 双端队列
- 优先队列
- 树
- 二叉树
- 二叉树的遍历
- 二叉树的递归序
- 二叉树的前序遍历（递归）
- 二叉树的前序遍历（非递归）
- 二叉树的中序遍历（递归）
- 二叉树的中序遍历（非递归）
- 二叉树的后序遍历（递归）
- 二叉树的后序遍历（非递归）
- 二叉树的广度优先遍历（BFS）
- 平衡二叉树
- 二叉搜索树
- 满二叉树
- 完全二叉树
- 二叉树的打印（二维数组）
- 树的序列化和反序列化
- 前缀树
- 堆
- Java系统堆优先队列
- 集合数组实现堆
- 图
- 图的定义
- 图的存储方式
- 图的Java数据结构（邻接表）
- 图的表达方式及对应场景创建
- 图的遍历
- 图的拓扑排序
- 图的最小生成树之Prim算法
- 图的最小生成树之Kruskal算法
- 图的最小单元路径之Dijkstra算法
- 位图
- Java实现位图
- 并查集
- Java实现并查集
- 滑动窗口
- 单调栈
- 排序
- 冒泡排序BubbleSort
- 选择排序SelectSort
- 插入排序InsertSort
- 插入排序InsertXSort
- 归并排序MergeSort
- 快速排序QuickSort
- 快速排序优化版QuickFastSort
- 堆排序HeapSort
- 哈希Hash
- 哈希函数
- guava中的hash函数
- hutool中的hash函数
- 哈希表实现
- Java之HashMap的实现
- Java之HashSet的实现
- 一致性哈希算法
- 经典问题
- 荷兰国旗问题
- KMP算法
- Manacher算法
- Go