小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Java
  5. 正文

Java语言程序设计(进阶)(第七章)整理

2018年4月16日 1434点热度 0人点赞 0条评论

第七章:深入集合Collection

7.1 集合框架与ArrayList

如图1所示,是Java常见的一些集合框架的类。最上面是Collection,它有两个子接口,List和Set。这些List有一些类来实现这个借口,比如说AbstractList,在AbstractList下面还有Vector Stack,还有ArrayList等。但是对于set这个接口来说,下面也实现了很多类。最右端是Map这个借口,实现它的有HashMap等等。

1523867566600983.jpg

图1

1.ArrayList

List借口的可变数组实现。实现了所有可选列表操作,并允许包括null在内的所有元素,它是非线程安全。它的底层使用的数据结构是数组,适合查找修改,弱于删减。

例:ArrayList实现分析

//用指定的元素替代此列表中指定位置上的元素
//并返回以前位于该位置上的元素
public E set(int index, E element){
       RangeCheck(index);//检查index是否合法
      
       E oldValue = (E) elementData[index];
       elementData[index] = element;
       return oldValue;
}
//将指定的元素添加到此列表的尾部
//直接添加速度快
public boolean add(E e){
       ensureCapacity(size+1);//确保容量满足
       element[size++] = e;
       return true;
}

第四行是用来检查index是否符合范围要求。下面这一行取出index值保存在oldValue中,将下标为index的值设置为新的,然后把旧的元素值返回。

下面是增加元素的方法。首先确保还有一个额外容量,然后把值赋值给最后一个元素,返回true代表增加成功了。

//将指定的元素插入此列表中的指定位置。
//如果当前位置有元素,则右移当前位于该位置上的元素
//以及后续所有元素(即将索引加1)
//涉及数组拷贝,插入速度不及add方法
public void add(int index, E element){
       if(index>size)||index <0){
              throw new IndexOutOfBoundsException("Index:"+index+",
              Size:"+size);
              }
       //如果数组长度不足,进行扩容
       ensureCapacity(size+1);
       System.arraycopy(elementData, index,elementData,index+1,size-index);
       elementData[index] = element;
       size++;
}

首先判断下标index是否大于尺寸,或者index小于0,这就说明数组长度不足,需要对数组进行扩容,这个时候就抛出一个错误来。接下来确定数组的容量是能够容纳的。arraycopy就是把列表中若干值进行拷贝,也就是说所有元素往后拷贝1位。然后把值复制给空的那个地方。这样的操作代价还是很大的,所以性能并不好。

//数组扩容,1.5倍方式扩容。涉及数组拷贝,速度慢
public void ensureCapacity(int minCapacity){
       modCount++;
       int oldCapacity = elementData.length;
       if(minCapacity > oldCapacity){
              int newCapacity = (oldCapacity*3)/2+1;
              if(newCapacity < minCapacity)
                     newCapacity = minCapacity;
       elementData = Arrays.copyOf(elementData, newCapacity);
       }
}

    获取旧容量大小给oldcapacity。如果指定最小的容量比原有还要大,那么先扩大1.5,如果扩充后这个长度比需要的最小长度还要小,那么直接设置为mincapacity的大小。然后把原来列表的数据直接复制给新的数组。

7.2 LinkedList

LinkedList是List借口的链接列表实现,它可以实现所有的可选列表操作,并且允许所有元素(包括null),它实现Deque借口,为add、poll提供FIFO队列操作以及其他堆栈和双端队列操作。该实现是非线程安全的。当我们在编程序时,如果用到这个链表,并且是多线程去访问这个链表的时候,需要自己加XX(没听清),LinkedList不做同步与互斥来控制,需要你自己写程序来解决这个问题。它适合增减,弱于查改。

例:LinkedList数据结构

private transient Entry<E> header = new Entry<E>(null,null,null);
private static class Entry<E>{
       E element;
       Entry<E> next;
       Entry<E> previous;
       /***
       *构造方法:目标对象paramE将被防止在paramEntry1之前,
       *paramEntry2之后
       */
       Entry(E paramE, Entry<E>paramEntry1,Entry<E>paramEntry2){
              this.element = paramE;
              this.next = paramEntry1;
              this.previous = paramEntry2;
       }
}

header是链表的头,三个空在后面有指。这个结点中包含三个元素,element是值,next是当前节点的下一个节点是什么,previous是前一根节点是什么。后面的构造方法指定了这三个元素的内容。

//根据序号获取Entry对象
private Entry<E> entry(int paramint){
       if((paramint<0)||(paramint>=this.size)){
              throw new indexOutOfBoundsException("Index:"+paramint+",
              size:"+this.size);
       }
       Entry localEntry = this.header;
       int i;
       //最多遍历size/2个元素
       if(paramint<this.size>>1){
              for(i = 0; i<=paramint;i++)
                     localEntry = localEntry.next;
       }else{
              for(i=this.size;i>paramint;i--)
                     localEntry = localEntry.previous;
       }
       return localEntry;
}

这个方法是用来根据给定序号获取这个节点的值。首先判断序号是否越界,若越界则抛出异常类,否则继续进行。然后先设置链接到链表的头部,也就是从头部开始进行遍历。然后开始判断所给定的序号比列表一半的长度小还是长度达。若比长度右移一位(this.size>>1代表右移一位,实际上也就代表着长度除以2,这是我们在学二进制的时候就学过的)小,那么就从表头开始,一步一步往下找,直到找到我们需要的序号的元素,然后输出值。若大于,则同理。

/***
*要添加的元素:paramE
*目标对象:paramEntryEntry
*特点:插入速度快
*/
private Entry<E> addBefore(E paramE, Entry<E> paramEntry){
       //要添加的对象,设置其previous和next
       Entry localEntry = new Entry(paramE, paramEntry, paramEntry.previous)
      
       localEntry.previous.next=localEntry;
       localEntry.next.previous = localEntry;
      
       this.size+=1;
       this.modCount+=1;
       return localEntry;
}

实例化一个新的节点,这个时候我们必须指定这个结点放在哪里。

//指定位置添加元素,需要先找到index的元素,然后添加
public void add(int index, E element){
       addBefore(element,(index==size?header:entry(index)));
}
//队首添加元素
public void addFirst(E paramE){
       addBefore(paramE,this.header.next);
}
//队尾添加元素
public void addLast(E paramE){
       addBefore(paramE, this.header);
}
 
public E remove()
{
       return removeFirst();
}//删除第一个
public E remove(int index){
       return remove(entry(index));
}//删除第index个元素
public E removeFirst(){
       return remove(header.next);
}
public E removeLast(){
       return remove(header.previous);
}//删除最后一个

List的适用范围

(1)ArrayList适用于对于数据查询修改大于数据增加删除的场合;

(2)LinkedList适用于对于数据增删大于数据查询的场合。

7.3 HashMap与HashTable

1.HashMap(哈希映射)

它是基于哈希表的Map借口的实现,提供所有可选的映射操作,并允许使用null值和null键。它是非线性安全的。它不保证映射的顺序,特别是不保证顺序恒久不变的。HashMap的数据结构如图2所示。

1523867648129678.jpg

图2

代码描述版:

transient Entry[] table;
 
static class Entry<K,V> implements Map.Entry<K,V>{
       final K key;
       V value;
       Entry<K,V> next;
       final int hash;
       //......剩余代码
}

第一行就是设置一个数组,类型是Entry。第二行说明这个Entry。后面说明是Entry是一个列表等等。

总结来说,HashMap底层就是一个数组结构,数组中的每一项又是一个链表,先建一个的时候就会初始化这么一个数组,Entry就是数组中的元素,那么每个Map Entry就是一个K value对,它只有一个向下的指针来指示我们下一个元素,这就构成了链表。

例:如何向HashMap中添加元素

public V put(K key, V value){
       if(key==null)//null键视为相同的键
              return putForNullKey(value);//根据key的keycode重新计算hash值
       int hash = hash(key.hashCode());//搜索指定hash值在对应table中索引
       int i = indexFor(hash,table.length);
//如果i索引处的Entry不为null,通过循环不断遍历e元素的下一个元素
       for(Entry<K,V>e=table[i];e!=null;e=e.next){
              Object k;//key重复出现则更新其value
              if(e.hash ==hash&&((k=e.key)==key||key.equals(k))){
                     V oldValue = e.value;
                     e.value =value;
                     e.recordAccess(this);
                     return oldValue;
              }
       }
       modCount++;
       addEntry(hash,key,value,i);
       return null;
}

例:hash函数,加入高位计算,防止地位不变,高位变化时,造成hash冲突

代码:

static int hash(int h){
       h^=(h>>>20)^(h>>>12);
       return h^(h>>>7)^(h>>>4);
}
 
void addEntry(int hash, K key, V value, int bucketIndex){
       //获取指定bucketIndex索引处的Entry
       Entry<K,V>e=table[bucketIndex];
       //将新创建的Entry放入bucketIndex索引处,并让新的Entry指向原来的Entry
       table[bucketIndex] = new Entry<K,V>(hash,key,value,e);
       //如果Map中的key-value对的数量超过了极限
       if(size++>=threshold)
              //把table对象的长度扩充到原来的2倍
              resize(2*table.length);
}
//根据hash值查找对应的table位置
static int indexFor(int h, int length){
       return h&(length-1);
}

例:HashMap的get操作

public V get(Object key){
       if(key==null)
              return getForNullKey();
       int hash =hash(key.hashCode());
       for(Entry<K,V>e = table[indexFor(hash,table.length)];
       e!=null;
       e=e.next){
              Object k;
              if(e.hash==hash&&((k=e.key)==key||key.equals(k)))
                     return e.value;
       }
       return null;
}

2.HashTable(哈希表)

    HashTable和HashMap采用相同的存储机制,二者的实现基本一致。但是HashTable不允许NULL存在。HashTable是线程安全的,内部的方法基本都是synchronized。它的迭代器具有强一致性。

7.4 TreeMap与LinkedHashMap

1.TreeMap

它实际上是Map接口的树实现,不允许null值存在,非线性安全,键值有序。它的数据结构实际是采用了红黑二叉树,是一个自平衡二叉查找树,在进行插入和删除操作时,通过特定的操作能够保持二叉查找树的平衡,从而获得较高的查找性能。它的优点是做查找、插入和删除操作的时间是O(logn)。

如图3所示,Entry是红黑树的结点,它包含了红黑树的6个基本组成成分:key、value、left(左孩子)、right(右孩子)、parent、color。Entry节点根据key进行排序,本身entry节点包含的内容为value。红黑树排序时,根据entry中的key进行排序,entry中的key比较大小是根据比较器comparator来进行判断的。

1523867700555969.jpg

图3

TreeMap的优点:

(1)空间利用率高:HashMap的数组大小必须为2的n次方;TreeMap中树的每一个节点就代表了一个元素。

(2)性能稳定:Hash碰撞会导致HashMap查询开销提高;HashMap扩容时会rehash,开销高;TreeMap的操作均能在O(logn)内完成。

2.LinkedHashMap

Map接口的哈希表和链接列表实现,提供所有可选的映射操作,并允许使用null值和null键,非线程安全,具有可预知的迭代顺序。

例:LinkedHashMap实现分析

如图4所示。

1523867722709780.jpg

图4

HashMap第一级是数组,第二级是单向链表;而这个第二级结构是一个双向链表。

3.Map的适用范围

(1)HashMap适用于一般的键值映射需求;

(2)HashTable适用于有多线程并发的场合;

(3)TreeMap适用于要按照键排序的迭代场合;

(4)LInkedHashMap适用于特殊顺序的迭代场合(如LRU算法)。

7.5 HashSet

1.HashSet

它实现Set借口,由哈希表支持,允许使用null元素。非线程安全,不保证set的迭代顺序,特别是不保证该顺序恒久不变。

例:HashSet的实现分析

1523867741571214.jpg

图5

2.Set的特点

(1)HashSet通过HashMap实现;

(2)TreeSet通过TreeMap实现;

(3)LinkedHashSet通过LinkedHashMap实现;

(4)Set类与Map类拥有近似的使用特性。

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: Java
最后更新:2018年4月16日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
day7练习1:使用管道实现父子进程间通信,完成:ls | wc –l。 《新少林寺》观后感 [Leetcode]copy list with random pointer C++面向对象程序设计课程笔记(第一周) 博客图片库全部更新为新地址通知 班级记忆百宝箱第一版网站架设完毕
标签聚合
leetcode 高中 学习 Python python学习 算法 生活 鸟哥的linux私房菜 linux Java
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号