HashMap浅析?
这里是修真院后端小课堂,每篇分享文从 【背景介绍】【知识剖析】【常见问题】【解决方案】【编码实战】【扩展思考】【更多讨论】【参考文献】 八个方面深度解析后端知识/技能,本篇分享的是: 【HashMap浅析?】 大家好,我是IT修真院武汉分院学员,一枚正直善良的JAVA程序员。 今天给大家分享一下,修真院官网JAVA任务10中的深度思考,HashMap浅析? 一、背景介绍 HashMap的存储结构是由数组和链表共同组成的。所以HashMap有两张存储方式。可以中和数组和链表的优缺点。 数组的存储方式在内存的地址是连续的,大小固定,一代分配后不能被其他引用占用。特定是查询快,时间复杂度是O(1),插入和删除的操作比较慢,时间复杂度是O(n),链表的存储方式是非连续的,大小不固定,特定与数组相反,插入和删除快,查询速度慢。 HashMap的基本原理 首先判断Key是否为null,如果是,直接查找Entry[0],如果不是,先计算Key的HashCode,然后经二次Hash。得到Hash值,这个Hash的特征值是一个int值。 根据Hash值,对Entry[]的长度求余,得到Entry数组的index。 找到对应的数组,就找到对应的链表,然后按链表的操作对Value进行插入、删除和查询操作。 二.知识剖析 hash的功能是要保证元素尽量的在桶(buckets)中均匀分配。 Entry table 在第一次使用的时候被初始化,之后如果需要还可以调整大小,长度通常是是2的乘方。(某些情况下也可以为0。) threshold根据当前初始化大小和家长因子计算的边界大小。当桶中的键值对超过这个大小就进行扩容。 Node节点。 initial capacity是hash table中被创建的buckets的数量。load factor是用来衡量在capacity自动增长前,hash table可以被使用多少。当hash table中的entries使用数超过了load factor,capacity就会被重新hash,这样hash table的大小将成为之前两倍左右。 capacity(buckets的数量)和size(键值对的数量)的加和,会使迭代集合视图。所以不要把初始化大小设置过大,load factor也不要设置过小。0.75在时间和空间上是个比较好的数值。 HashMap是不同步的,如果多个线程同时并发访问一个hash map,当修改结构(不包括修改map的value)时必须在外部同步。 下面是一个单向链表。可以通过下面的连接找到其于的双向链表,双端链表代码。 package com.example.t; /** ?* Created by Administrator on 2018/8/9. ?*/ public class OrderLinkedList { ? ? private Node head; ? ? private class Node{ ? ? ? ? private int data; ? ? ? ? private Node next; ? ? ? ? public Node(int data){ ? ? ? ? ? ? data = data; ? ? ? ? } ? ? } ? ? public OrderLinkedList(){ ? ? ? ? head = null; ? ? } ? ? //插入节点,按照从小到大的顺序排列。 ? ? public void insert(int value){ ? ? ? ? Node node = new Node(value); ? ? ? ? Node pre = null; ? ? ? ? Node current = head; ? ? ? ? while (current != null && value > current.data){ ? ? ? ? ? ? pre = current; ? ? ? ? ? ? current = current.next; ? ? ? ? } ? ? ? ? if (pre == null){ ? ? ? ? ? ? head = node; ? ? ? ? ? ? head.next = current; ? ? ? ? }else { ? ? ? ? ? ? pre.next = node; ? ? ? ? ? ? node.next = current; ? ? ? ? } ? ? } ? ? //删除头节点。 ? ? public? void deleteHead(){ ? ? ? ? head = head.next; ? ? } ? ? public void display(){ ? ? ? ? Node current = head; ? ? ? ? while (current != null){ ? ? ? ? ? ? System.out.print(current.data + " "); ? ? ? ? ? ? current = current.next; ? ? ? ? } ? ? ? ? System.out.println(); ? ? } } 三、常见问题 1.链表是什么? 四.解决方案 1.答:链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。 五。编码实战 六、参考文献 https://www.cnblogs.com/wuhuangdi/p/4175991.html https://www.cnblogs.com/o-andy-o/p/3437101.html https://www.cnblogs.com/coder2012/p/3954736.html https://www.cnblogs.com/ysocean/p/7928988.html 8.更多讨论 8.更多讨论 1. 什么是单向链表? 答:每个节点中只保存指向下一个节点的引用。 public class OrderLinkedList { ? ? private Node head; ? ? private class Node{ ? ? ? ? private int data; ? ? ? ? private Node next; ? ? ? ? public Node(int data){ ? ? ? ? ? ? data = data; ? ? ? ? } ? ? } ? ? public OrderLinkedList(){ ? ? ? ? head = null; ? ? } //some code ?} 2. 什么是双向链表。 答:每个链节中保存了这个链节前后链节的引用。可以通过一个链节向前或向后查询。 public class TwoWayLinkedList { ? ? ? private Node head;//表示链表头 ? ? ? private Node tail;//表示链表尾 ? ? ? private int size;//表示链表的节点个数 ? ? ? ? ? ? ? private class Node{ ? ? ? ? ? private Object data; ? ? ? ? ? private Node next; ? ? ? ? ? private Node prev; ? ? ? ? ?? ? ? ? ? ? public Node(Object data){ ? ? ? ? ? ? ? this.data = data; ? ? ? ? ? } ? ? ? } ? ? ?? ? ? ? public TwoWayLinkedList(){ ? ? ? ? ? size = 0; ? ? ? ? ? head = null; ? ? ? ? ? tail = null; ? ? ? } //some code } ?23? ? ? 3.双端链表和双向链表的差别? 答:双端链表的查询方向是头部-->尾部,和尾部-->头部。双向链表是每个链节都可以向两个方向查询。 4.使用HashMap时需不需要指定初始大小。 答:看情况。根据业务需求。 PPT链接?视频链接 更多内容,可以加入IT交流群565734203与大家一起讨论交流 这里是技能树·IT修真院:,初学者转行到互联网的聚集地 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |