JAVA源码走读(一) HashMap与ArrayList

简介: HashMap 一、HashMap基本概念: HashMap是基于哈希表的Map接口的实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

HashMap

一、HashMap基本概念:

HashMap是基于哈希表的Map接口的实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

HashMap不是线程安全的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

Map map = Connections.synchronized(new HashMap());

 

二、HashMap的数据结构

HashMap的底层主要是基于数组和链表来实现的,它之所以又相当快的查询速度是因为它是通过计算散列码来决定存储的位置。

在构造HashMap的时候如果我们指定了加载因子和初始容量的话就调用第一个构造方法,否则的话就是用默认的。默认初始容量为16,默认加载因子为0.75。

 

三、HashMap的存储结构

 

public V put(K key, V value) {
     // 若“key为null”,则将该键值对添加到table[0]中。
         if (key == null)
            return putForNullKey(value);
     // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。
         int hash = hash(key.hashCode());
     //搜索指定hash值在对应table中的索引
         int i = indexFor(hash, table.length);
     // 循环遍历Entry数组,若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!
         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
             Object k;
              if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同则覆盖并返回旧值
                  V oldValue = e.value;
                  e.value = value;
                  e.recordAccess(this);
                  return oldValue;
              }
         }
     //修改次数+1
         modCount++;
     //将key-value添加到table[i]处
     addEntry(hash, key, value, i);
     return null;
}

我们一般对哈希表的散列很自然地会想到用hash值对length取模(即除法散列法),Hashtable中也是这样实现的,这种方法基本能保证元素在哈希表中散列的比较均匀,但取模会用到除法运算,效率很低,HashMap中则通过h&(length-1)的方法来代替取模,同样实现了均匀的散列,但效率要高很多,这也是HashMap对Hashtable的一个改进。

 

ArrayList

一、首先是ArrayList的继承体系:

public class ArrayList<E> extends AbstractList<E> implements List<E>,RandomAccess,Cloneable,java.io.Serializable

public class ArrayList<E> extends AbstractList<E> implements List<E>,RandomAccess,Cloneable,java.io.Serializable

 

二、增加一条数据,因为数组长度一旦定义则不能够变化,所以使用了ensureCapacity方法来确保数组能动态变化,通过Arrays.copyOf拷贝到新的数组 容量size+1方法源码:

 

public void ensureCapacity(int minCapacity){
       modCount++;
       int oldCapacity = elementData.length; //得到目前数组的容量大小
       if(minCapacity > oldCapacity){ //如果目前数组容量小于传入的参数minCapacity
              Object oldData[] = elementData;
              Int newCapacity = (oldCapacity *3) /2 + 1 则新生成一个容量
               If(newCapacity < minCapacity) //如果新生成的容量依旧小于传入的残水
                      NewCapacity = minCapacity; //将参数赋予这个新容量
                            elementData = Arrays.copyOf(elementData,newCapacity);//将数组扩大到newCapacity的长度。
         }
     }
}

三、contains方法用来判断ArrayList中对象o是否在,调用了indexOf来实现

      public int indexOf(Object o){
              if(null == 0){ //如果o为null
                     for(int I = 0;i < size;i++){  //循环遍历ArrayList底层的数组
                            if(elementData[i] == null){
                                   return i;
                            }else {
                                   for(int i = 0;I < size;i++){
                                     if(o.equals(elementData[i])){ //若发现其中某个元素等于o,则返回该元素的索引
                                         return i;
         }
        }

四、删除一个元素且不说最好一个元素则需要移动底层数组,这个会导致效率低下,故ArrayList不适合删除操作过多的场景.

public E remove(int index){
         RangeCheck(index);   //检查索引边界
         modCount++;
         E oldValue = (E)elemetData[index]; //得到index上的元素
         Int numMoved = size – index -1; //得到需要移动的元素熟练,注意这里要减1,因为不包括要删除的元素

    If(numMoved > 0) //需要移动的元素数量大于0,则开始移动ArrayList底层数组   System.arraycopy(elementData,index+1,elementData,index,numMoved);
      elementData[--size] = null;
   return oldValue;
}

 

目录
相关文章
|
4月前
|
人工智能 安全 JavaScript
Java ArrayList:动态数组
本文探讨Java中的数组,对比C/C++、JS/PHP/Python等语言的数组特性。文章分析了Java数组的定义、创建方式及其规范,指出其优缺点。Java数组作为引用类型,在堆上分配内存,支持动态大小,避免了C/C++中裸数组的常见问题(如越界访问)。然而,Java数组也存在性能瓶颈和设计缺陷,例如运行时的安全检查影响速度,无法创建超大数组或泛型数组,且多线程场景下缺乏同步机制。作者建议在实际开发中用集合替代数组以规避这些问题。
114 1
|
5月前
|
前端开发 Java 关系型数据库
基于Java+Springboot+Vue开发的鲜花商城管理系统源码+运行
基于Java+Springboot+Vue开发的鲜花商城管理系统(前后端分离),这是一项为大学生课程设计作业而开发的项目。该系统旨在帮助大学生学习并掌握Java编程技能,同时锻炼他们的项目设计与开发能力。通过学习基于Java的鲜花商城管理系统项目,大学生可以在实践中学习和提升自己的能力,为以后的职业发展打下坚实基础。技术学习共同进步
418 7
|
5月前
|
消息中间件 算法 安全
JUC并发—1.Java集合包底层源码剖析
本文主要对JDK中的集合包源码进行了剖析。
|
5月前
|
人工智能 安全 Java
智慧工地源码,Java语言开发,微服务架构,支持分布式和集群部署,多端覆盖
智慧工地是“互联网+建筑工地”的创新模式,基于物联网、移动互联网、BIM、大数据、人工智能等技术,实现对施工现场人员、设备、材料、安全等环节的智能化管理。其解决方案涵盖数据大屏、移动APP和PC管理端,采用高性能Java微服务架构,支持分布式与集群部署,结合Redis、消息队列等技术确保系统稳定高效。通过大数据驱动决策、物联网实时监测预警及AI智能视频监控,消除数据孤岛,提升项目可控性与安全性。智慧工地提供专家级远程管理服务,助力施工质量和安全管理升级,同时依托可扩展平台、多端应用和丰富设备接口,满足多样化需求,推动建筑行业数字化转型。
192 5
|
8天前
|
存储 小程序 Java
热门小程序源码合集:微信抖音小程序源码支持PHP/Java/uni-app完整项目实践指南
小程序已成为企业获客与开发者创业的重要载体。本文详解PHP、Java、uni-app三大技术栈在电商、工具、服务类小程序中的源码应用,提供从开发到部署的全流程指南,并分享选型避坑与商业化落地策略,助力开发者高效构建稳定可扩展项目。
|
2月前
|
Java 索引
Java ArrayList中的常见删除操作及方法详解。
通过这些方法,Java `ArrayList` 提供了灵活而强大的操作来处理元素的移除,这些方法能够满足不同场景下的需求。
368 30
|
5月前
|
存储 Java
【源码】【Java并发】【ThreadLocal】适合中学者体质的ThreadLocal源码阅读
前言 下面,跟上主播的节奏,马上开始ThreadLocal源码的阅读( ̄▽ ̄)" 内部结构 如下图所示,我们可以知道,每个线程,都有自己的threadLocals字段,指向ThreadLocalMap
454 81
【源码】【Java并发】【ThreadLocal】适合中学者体质的ThreadLocal源码阅读
|
5月前
|
前端开发 Java 物联网
智慧班牌源码,采用Java + Spring Boot后端框架,搭配Vue2前端技术,支持SaaS云部署
智慧班牌系统是一款基于信息化与物联网技术的校园管理工具,集成电子屏显示、人脸识别及数据交互功能,实现班级信息展示、智能考勤与家校互通。系统采用Java + Spring Boot后端框架,搭配Vue2前端技术,支持SaaS云部署与私有化定制。核心功能涵盖信息发布、考勤管理、教务处理及数据分析,助力校园文化建设与教学优化。其综合性和可扩展性有效打破数据孤岛,提升交互体验并降低管理成本,适用于日常教学、考试管理和应急场景,为智慧校园建设提供全面解决方案。
382 70
|
4月前
|
JavaScript Java 关系型数据库
家政系统源码,java版本
这是一款基于SpringBoot后端框架、MySQL数据库及Uniapp移动端开发的家政预约上门服务系统。
153 6
家政系统源码,java版本
|
3月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
192 3