HashMap简介

刺骨的言语ヽ痛彻心扉 2023-07-02 04:29 27阅读 0赞

## HashMap简介 ##

在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。  
适用场景：读多写少，（读取多插入少）  
一般场景 --》 一次写入，剩下全读。  
读取速度最快的，是根据下标读数组，时间复杂度O(1) ，但是插入速度慢。  
大概结构上个图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw_size_16_color_FFFFFF_t_70]  
但实际的结构构造要比这复杂的多，涉及到红黑树结构。（找了个大概的图，先了解下。）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw_size_16_color_FFFFFF_t_70 1]  
接下来复习下几种基础结构：

**数组**：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)  
**数组优缺点总结**  
优点：  
1、按照索引查询元素速度快  
2、能存储大量数据  
3、按照索引遍历数组方便  
缺点：  
1、根据内容查找元素速度慢  
2、数组的大小一经确定不能改变。  
3、数组只能存储一种类型的数据  
4、增加、删除元素效率慢  
5、未封装任何方法，所有操作都需要用户自己定义。  
**线性链表**：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。  
**红黑树**：  
　　红黑树是一种自平衡二叉查找树，是一种数据结构，典型的用途是实现关联数组，存储有序的数据。它是在1972年由Rudolf Bayer发明的，别称" 对称二叉B树 "，它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的。它可以在 O(logn) 时间内做查找，插入和删除，这里的n是树的结点个数。  
（了解了解，这里不做展开。）

**加粗样式**数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构  
（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式）  
**哈希表的主结构是数组+链表：**  
哈希表利用了在数组中根据下标查找某个元素，一次定位就可以达到。  
**哈希冲突**  
当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。  
哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀。  
数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。HashMap是采用了链地址法，也就是**数组+链表的方式**。

**散列操作：**  
散列：没有规律的分散开，又分布比较均匀。  
例如 数组有5个空间，30 个数据，例如：利用 X%6 求得散列值  
然后利用链表存放。  
一般是对奇数进行取余操作。  
**散列碰撞** ：多个数据集中存在数组的一个空间内，即称为散列碰撞。  
**数据倾斜**：数据一直只向一个数组空间里边插入，（这就和单链表没什么区别了吧，哈哈哈，降低了哈希表的性能）  
HashMap也有机制来应对，它会规定一个链表的最长长度，如果超出，会申请一个长度为原来2倍的数组，将数据重新散列进去（原来的数组和链表结构会被回收）称为**重哈希过程**，时间复杂度 达到O(n)级别。

当链表的长度超过一定的数值 (在java中超过8) 就会转换为用红黑树存储，链表和红黑树是同时存在的。  
当HashMap存储的数据的个数达到某个数值的之后，会再一次进行重哈希过程。  
这种机制，相比于之前说的，（当哈希表中的某个链表达到某个值时候，再重哈希）的次数更少。  
当然前边散列函数写得好的话，表的存储的节点总量和每个空间里边的节点个数是呈线性关系的。

这里实现一下最简单的hashmap原理代码

public class HashMap <KEY , VALUE>{
    	public Link <KEY  , VALUE > [] data = new Link();
    	public void put(KEY  a  ,   VALUE  b){
        	int s = a.hashCode();
        	s = s%data.length;    // 最简单的散列函数
        	Link <KEY  , VALUE > newnode = new Link();
        	newnode.key = a;
        	newnode.value = b;
        	if(data[s] == null){
        		data[s] = new node;
        	}else{
    			new node.next = data[s];
                 data[s] = new node;
    		}
        }
        
        public  VALUE get(){
        	VALUE re = null;
        	int s = a.hashCode();
        	s = s%data.length;  //通过散列找到该节点
        	Link <KEY  , VALUE > newnode = data[s] ;
        	while( newnode !=null ){
    			if( newnode.key == a ){
    			 		re = newnode.value;
    			 		break;
    			}else{
    					newnode = newnode.next;
    			}
      		}
         }
    }

public class Link <KEY , VALUE> {
    	public KEY key;
    	public VALUE value;
    	public Link next;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200126162339747.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020012616254552.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZyaXN0amNqZG5jZw==,size_16,color_FFFFFF,t_70