JAVA源码走读(一) HashMap与ArrayList

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏coolblog.xyz技术专栏

ArrayList 源码详细分析

ArrayList 是一种变长的集合类,基于定长数组实现。ArrayList 允许空值和重复元素,当往 ArrayList 中添加的元素数量大于其底层数组容量时...

4288
来自专栏算法与数据结构

数据结构 单链表&顺序表

顺序表: 一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。 优点:在于随机访问元素, 缺点:插入和和删除的时候,需要移动大量的元素。 链表...

46410
来自专栏Java学习123

【数据结构】ArrayList原理及实现学习总结

8455
来自专栏用户画像

6.2.2 折半查找

折半查找,又称二分查找,它适用于有序的顺序表。基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则...

641
来自专栏Android研究院

数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)

比如:美女和野兽,抽象的事物表示美女:头发长 前凸后翘。。。 可以表示为一个数据单元,野兽也是一个数据单元。

2451
来自专栏撸码那些事

【图解数据结构】 线性表

2053
来自专栏大数据和云计算技术

算法基础6:二叉树查找

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第6篇《二叉树查找》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法基...

3625
来自专栏小灰灰

JDK容器学习之TreeMap (一) : 底层数据结构

TreeMap 在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 Linke...

2459
来自专栏码匠的流水账

聊聊storm nimbus的mkAssignments

storm-2.0.0/storm-server/src/main/java/org/apache/storm/daemon/nimbus/Nimbus.jav...

1202
来自专栏有趣的Python

算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重...

3166

扫码关注云+社区

领取腾讯云代金券