学习目的
- 了解集合的概念
- 掌握java集合的分类以及作用
- 掌握java集合的对象创建,以及常用方法的使用
- 熟悉java每一种集合的使用场景
- 掌握常见的集合ArrayList、LinkedList、HashSet 、TreeSet、HashMap、Properties、TreeMap
- 学会查看集合的底层源代码
- 掌握从集合底层的数据结构与实现来洞悉equals()方法与hashCode()方法的重写
一.集合
-
Java 集合的继承结构体系
主要分为两大类:Collection 和 Map。
集合总结构图.png
子类 | 父类/接口 | 特点(源码实现) |
---|---|---|
Iterable | 提供Iterator()方法,返回当前集合的迭代器对象 | |
Collection | Iterable | Set、List集合的父类接口,以单个元素存储数据 |
List | Collection | 底层是数组,存取有序,元素可重复 |
ArrayList | List | 底层是数组,方便查找;非线程安全 |
LinkedList | 底层是双向链表,方便插入和删除 | |
Vector | synchronized修饰,线程安全版本的ArrayList | |
Stack | Vector | 已弃用 |
Set | Collection | 底层是数组,存取无序,元素不可重复 |
HashSet | Set | 底层是HashMap,HashSet存入的元素 = HashMap的key部分;非线程安全 |
SortedSet | 存取无序,元素不可重复,但存入的元素可以排序 | |
TreeSet | SortedSet | 底层是TreeMap |
- | - | |
Map | 以键值对key-value 形式存储数据,key部分 = set集合 | |
Hashtable | Map | 底层是哈希表,synchronized修饰,线程安全 |
Properties | Hashtable | 底层是HashMap,key和value都只能存储字符串String形式的数据;线程安全 |
HashMap | Map | 底层是哈希表,线程不安全 |
SortedMap | ||
TreeMap | SortedMap | 底层是二叉树,TreeMap的key可以自动按照大小排序 |
- 集合的主要常用类型
- List:有序集合(存入顺序和取出顺序相同),可以存放重复的数据;
- Set:无序集合(存入顺序和取出顺序不同),不允许存放重复的数据;
- Map:无序集合,以键-值对形式存放数据。集合中包含一个键对象,一个值对象,键对象不允许重复,值对象可以重复。
- 集合与数据结构
每一种集合在底层都对应着不同的数据结构,即每一种集合对数据的存储方式都不一样,因此效率和性能也不一样。不同的数据结构,数据存储方式不同。
- 数组:ArrayList,Vector;有序,可重复,查询快;
- 二叉树:TreeSet,TreeMap;无序,可排序;
- 链表:LinkedList;无序,不可重复,增删快;
- 哈希表:HashSet,HashMap,Hashtable;无序,不可重复,增删查询综合较快;
- 图:Map;无序;
- 数组+链表/树:HashSet,HashMap,综合数组、链表、树的特点;
- 栈:Stack;已失效。
-
集合在程序中的应用
集合与数据库数据的底层实现.png - 集合的选择
- 以单个方式存储元素:Collection及其子类;
- 以键值对方式存储元素:Map及其子类;
- 线程安全:Hashtable、Properties;
- 非线程安全:ArrayList、HashSet、HashMap。
- 集合之间的转换
- 查看每个集合底层的源码,查看构造方法,keySet()、entrySet()方法等。
1.1 Collection
- 概念
Collection是集合层次结构中的根接口,是 List 和 Set 的父接口,LIst 和 Set都继承了Collection接口的属性和方法。而Collection同时也继承于Iterable接口,并且实现其Iterator()方法,该方法返回得到一个迭代器对象。通过迭代器对象,可以遍历所有的Collection集合中的元素。 -
Collection体系继承结构
Collection 集合继承结构图.png - 性质特点
- 单个元素存储:在Collection集合中,所有子类集合都是采用 **单个元素方式存储数据;
- 存储地址:所有的Collection子集合存储的元素都是"内存地址",而不是元素本身,不管该元素是基本类型还是引用类型**。
- Collection 接口常用方法
- Collection c = new LinkedList():面向接口编程,创建Collection对象;
- int size() :返回集合中元素的总个数;
- boolean isEmpty():判断集合是否为空,底层使用size属性==0判断;
- boolean add(Object o):往集合中添加单个元素;
- boolean remove(Object o):从集合中移除单个指定元素;
- void clear():移除集合对象中的所有元素;
- Object[] toArray() :将集合对象中所有元素返回为一个数组中;
- boolean contains(Object o):判断集合中是否包含指定元素;
- boolean equals(Object o):比较集合对象与指定对象o是否相等。
//创建一个数组集合对象
Collection c1 = new ArrayList();
String s1 = new String("abc");
String s2 = new String("efg");
c1.add(s1);
c1.add(s2);
System.out.println(c1.size());//输出2
String x = new String("abc");
/*c1.add(x);//往集合c中添加重复元素 abc
System.out.println(c1.size());//输出2
System.out.println(c1.contains(x));//c集合中是否包含x:true
/*
ArrayList底层的contains(Object o)方法中又使用equals()方法
o.equals(elementData[i]);//判断ArrayList是否已存在元素o
*/
- Iterator it = collection.iterator():最重要的方法,返回一个当前集合的迭代器,遍历当前集合;
//指定元素类型E的迭代器接口
Iterator<E> iterator() ;
//面向接口编程,创建Collection对象
Collection c = new ArrayList();
//创建一个可以在c对象上操作的迭代器对象
Iterator iter = c.iterator();
//迭代器遍历集合,若该集合有元素则输出
while (iter.hasNext()) {
Integer v = (Integer)iter.next();//对集合c进行迭代遍历得到的元素类型 转型成 Integer类型
System.out.println(v);
}
//for循环迭代器遍历集合,若该集合有元素则输出
for (Iterator iter1 = c.iterator() ; iter1.hasNext() ; ) {
Integer v = (Integer)iter1.next();
System.out.println(v);
}
1.1.1 List<列表>
- 概念
List是一个有序接口,意为列表或序列。List底层是数组存储元素,因此可以根据数组下标,对List中的每个元素进行位置插入、访问、搜索等。List是一个存入和输出顺序相同、可以存放重复数据的Collection集合。 - 分类
- ArrayList:数组列表,有序可重复,查询快;
- LinkedList:链表,有序可重复,增删快;
- Vector:向量,线程安全的ArrayList,但已被ArrayList淘汰;
- Stack:栈,已被LinkedList淘汰。
- 特点
- 可提供带下标索引的方法(底层是数组);
- 有序:元素存入和取出是相同的顺序;
- 可重复:可以加入重复的元素;
- 默认在集合的末尾添加元素。
List list = new ArrayList();
list.add(123);//在集合中添加元素,默认在集合末尾添加
list.add(666);
list.add("abc");
list.add(123);
list.add(88.88);
//在集合指定下标处 添加指定元素
list.add(4,999);
//创建在c集合上的迭代器对象,并迭代遍历c的所有元素
for ( Iterator it = list.iterator();it.hasNext();){
Object o = it.next();
System.out.print(o + " ");//加入与输出的顺序:123 666 abc 123 999 88.88
}
for (int i =0;i<list.size();i++){
//根据下标对list集合进行遍历
System.out.println(list.get(i));
}
3.1.1.1 ArrayList
- 概念
ArrayList是底层采用数组形式 的数据结构进行存储元素的集合,是一个可增长的数组,可以提供快速迭代和随机访问的能力。 - 特点
- 末尾添加元素:ArrayList底层的源码方法规定,在数组列表的末尾添加元素;
- 检索效率高:每个元素占用空间大小相同,内存地址连续的,知道首元素内存地址和下标,通过数学表达式计算出 元素的内存地址,因此检索效率最高;
- 非线程安全:ArrayList底层的方法都是无synchronized修饰的;
- 自动扩容:当ArrayList增加的元素过多,超出初始化的容量10时,会自动扩容,且每一次扩容是原来的1.5倍。
- 字段
- int DEFAULT_CAPACITY = 10:创建一个初始默认容量为10的ArrayList对象;
- Object[] EMPTY_ELEMENTDATA = {}:存储元素数据,初始为空元素数据容量的数组;
- Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}:默认空元素数据容量-添加元素后,默认容量=10;
- Object[] elementData:ArrarList底层实际用于存储元素的数组;
- 常用方法
对于ArrayList常用的方法,可以到源码的java.util.ArrayList类中查看具体的实现,学会查看源码,理解源码。(其他类的常用方法亦如此)
//带参构造,创建并初始化指定容量大小的ArrayList对象
public ArrayList(int initialCapacity) {
}
//无参构造,创建默认空元素数据容量的ArrayList对象,添加元素后,默认容量也=10
public ArrayList() {
}
//返回数组长度-数组中元素的个数
public int size() {
return size;
}
//判断数组是否为空
public boolean isEmpty() {
return size == 0;
}
//判断数组是否包含指定元素--调用同类中的indexOf()方法
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//返回指定元素在数组中-第一次出现的下标
public int indexOf(Object o) {
}
//返回指定元素在数组中-最后一次出现的下标
public int lastIndexOf(Object o) {
}
//复制一份该数组-浅克隆
public Object clone() {
}
//按顺序+指定长度,将ArrayList中所有的元素-使用数组返回
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
//返回指定下标的元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//用指定的元素 替代 指定下标位置的元素
public E set(int index, E element) {
}
//将指定的元素添加到尾部,此方法限定ArrayList的添加元素特点
public boolean add(E e) {
}
//在ArrayList中指定位置添加元素
public void add(int index, E element) {
}
//移除、删除指定下标位置的元素,返回该元素
public E remove(int index) {
}
//删除指定下标位置的元素
public boolean remove(Object o) {
}
//清楚列表中的所有元素,清空列表
public void clear() {
}
//删除列表中指定 [ 范围)内的元素
protected void removeRange(int fromIndex, int toIndex) {
}
3.1.1.2 LinkedList
- 概念
LinkedList是底层采用 双向链表形式的数据结构存储元素,可以提供快速插入删除的能力。 - 特点
- 增删容易:地址不连续,使用节点保存数据和下一个节点的地址,删除时不需要移动每一个节点元素;
- 非线程安全:
- 由节点组成,节点保存数据和内存地址
- 链表图解
-
单链表
单向链表.png -
双链表:LinkedList底层的实现原理就是双向链表,采用内部类-节点的形式
双向链表.png
- 字段
- int size = 0:初始化链表长度为0;
- Node<E> first:前一个节点内存地址;
- Node<E> last:后一个节点内存地址;
- class Node<E>:静态内部类,静态内部节点。
- 常用方法
LinkedList常用方法与ArrayList常用方法差不多,基本都是创建对象的构造器,往集合中加元素、删元素、和查元素等,可查看底层源码了解方法的具体实现。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//静态内部类-节点
private static class Node<E> {
E item;//
Node<E> next;//下一节点内存地址
Node<E> prev;//前一节点内存地址
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
//无参构造
public LinkedList() {
}
//带参构造
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
//LinkedList底层采用 双向链表 的实现原理
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
}
3.1.1.3 Vector(非重要)
- 概念
Vector**底层采用数组形式 **的数据结构存储元素,意为向量,目前已极少使用。 - 特点
- 效率慢<性能低>:使用synchronized关键字修饰,需要额外处理安全问题导致直接操作数据的效率低下;
- 线程同步:Vector 中的方法都是使用synchronized关键字修饰的,是线程安全版本的ArrayList;
- 自动扩容:当Vector增加的元素过多,超出初始化的10时,会自动扩容,且每一次扩容是原来的两倍。
- 字段
- Object[] elementData:底层采用数组形式存储数据 ;
- int elementCount:该集合的总元素个数;
- int capacityIncrement:指定每次自动扩容的容量。
- 常用方法
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//构造器,可以创建不同形式、不同容量的Vector对象
public Vector(int initialCapacity, int capacityIncrement) { //指定初始化容量,且设定每次自动扩容的大小
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
public Vector(Collection<? extends E> c) {
}
//自动扩容实现原理
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
3.1.1.4 Stack(非重要)
- 概念
继承 Vector接口 实现的一个栈,结构是后进先出,目前已经被 LinkedList 取代。
3.1.2 Set
- 概念
Set的底层采用HashMap形式的数据结构存储元素的一个接口。是一个无序,不允许存放重复数据的集合。也是HashSet和TreeSet的父类接口。 - 特点
- 无序:无序指的是元素存入和取出的顺序不同。HashMap底层采用的是哈希算法对元素进行存储,哈希算法本身就具有无序的特点(散列性);
- 不允许重复:底层HashMap存储数据的形式是键值对,键key是无序且不允许重复的。而Set集合中存入元素 == HashMap中存key,因此Set集合与HashMap存储数据的特点是一样的。
- 常用方法
- int size():获取set集合中元素的个数;
- boolean isEmpty():判断集合是否为空,底层使用siz() == 0判断;
- boolean contains(Object o):判断集合中是否包含指定元素o;
- Iterator<E> iterator():产生一个在该set集合上的迭代器对象;
- Object[] toArray():将set集合中所有的算数转换成数组输出;
- boolean add(E e):往set集合中添加指定元素;
- boolean remove(Object o):从set集合中移除指定元素;
- void clear():清楚set集合中所有的元素;
- boolean equals(Object o):判断指定对象是否与该set集合对象相等。
public interface Set<E> extends Collection<E> {
// Query Operations
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
// Modification Operations
boolean add(E e);
boolean remove(Object o);
// Bulk Operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
// Comparison and hashing
boolean equals(Object o);
int hashCode();
}
3.1.2.2 HashSet
- 概念
HashSet即Hash + Set,使用哈希算法存储数据的Set集合。HashSet 底层使用的是HashMap[]存储数据。HashSet 中的数据是无序的,不可存放重复的数据,原因同Set。 - 特点
- 无序:数据存入顺序和读出顺序不相同,HashSet按照哈希算法存取数据,综合了数组和链表的特点,具有非常好的性能;
- 不可重复数据:底层采用HashMap存储元素,存入的元素 == HashMap中的key,key不能重复。
- 工作原理
当向 HashSet 中插入数据时,先调用对象的 hashCode() 方法得到该对象的哈希码,然后根据 哈希码 计算出该对象插入到集合中的位置。 - 代码解释
//面向接口编程,创建一个HashSet对象
Collection c = new HashSet();
//创建在c集合上的迭代器对象
Iterator it ;
c.add(123);//同理依次往Collection集合c中add():666 abc 456 new Object() 123 efg 456 88.88 efg
c.add(666);
//测试HashSet的无序(元素存入和取出是不同的顺序),以及不可重复(元素不能重复)
for (it = c.iterator();it.hasNext();){
Object o = it.next();//迭代遍历c集合上的所有元素
System.out.print(o + " ");
//存入和输出顺序:abc efg 456 java.lang.Object@4554617c 666 88.88 123
}
3.1.2.3 SortedSet
- 概念
SortedSet是一个继承于Set的接口,继承了Set接口的特性-无序,不可重复。但是存放到SortedSet集合中的元素<key部分>可以按照大到小的顺序自动排序,排序的元素需实现Comparable接口(重写compareTo()方法)或实现Comparator接口(重写compare()方法)。
3.1.2.4 TreeSet
- 概念
TreeSet底层采用 TreeMap[ ]形式 的数据结构存储数据的集合,TreeMap底层又是二叉树(红黑二叉树)。TreeSet 是可以对 Set 集合<key部分> 进行自动排序的一种集合,默认自动升序<从小到大升序>,但不可存放重复的数据。 - 特点
- 不可重复:因为TreeSet存入元素 = TreeMap的key,key不可重复;
- 对排序的 Set集合的元素类型只能是一种类型排序。如:Set集合中元素是 int 类型时,不能加入 String字符串类型,否则将无法排序;
- 无序,但可排序:无序指的是存入元素的顺序和取出来的顺序不一样,但是存入的元素会按照从小到大排序,也就是说排序后的顺序可能还是和存入的顺序不一样。
- 代码示例
public static void main(String[] args) {
Set set = new TreeSet();
set.add("a");//同理往set集合中add():aa d f bb c aa f
//foreach增强循环遍历set集合
for (Object s:set) {
System.out.print(s + " ");//输出a aa bb c d f
}
}
- 扩展
TreeSet集合中添加自定义类型的元素,有两种方法:
- 自定义类紧密实现Comparable接口,并重写其compareTo()方法,在方法内部写明比较规则。创建TreeSet集合时调用无参构造,初始化comparator对象为null。
Person p1 = new Person();
//构造器底层初始化Comparator对象为null
TreeSet<Person> h = new TreeSet<>();
h.add(p1);
//实现Comparable接口并重写compareTo()方法
class Person implements Comparable<Person>{
public int compareTo(Person p) { //比较规则 }
}
- 自定义类分离实现Comparator接口,并重写其compare()方法,在方法内部写明比较规则。创建TreeSet集合时调用带参构造,初始化comparator对象为new Comparator。
User u4 = new User();
UserComparator us = new UserComparator();//创建Comparator比较器对象
TreeSet<User> ts = new TreeSet<>(us);//构造器底层初始化Comparator
ts.add(u4);
class User{ }
//实现Comparator接口并重写compare()方法
class UserComparator implements Comparator<User>{
@Override
public int compare(User u1, User u2) { //比较规则}
}
3.2 Comparable 接口<TreeSet排序>
- 概念
当需要将自定义类型的元素放入到TreeSet集合中存储时,那么自定义类型的类 就必须要实现Comparable 接口,并且重写实现Comparable 接口的compareTo()方法。在compareTo()方法内重写的内容就是关于自定义类进行比较的规则。 - 实现Comparable接口的作用
- 对基本类型元素排序: TreeSet 会对放入集合中的元素进行排序,如基本类型的包装类和 String 在底层都实现了 Comparable 接口,自动实现升序排序;
- 对自定义类型元素排序:Comparable 接口还可以对TreeSet中的自定义数据类型进行排序,但需要实现Comparable接口。未实现而放入TreeSet 中时,会出现ClassCastException类型转换异常--自定义类型不能转换为comparator类型。
- 典型方法
- int compareTo(Object o) :自定义类重写compareTo() 后,根据其返回值确定自定义类的排序顺序;
- 返回 = 0:表示添加到TreeSet中的元素相等,不需要更换顺序;
- 返回 > 0:表示添加到TreeSet中的元素,左边大于右边,升序排序;
- 返回 < 0:表示添加到TreeSet中的元素,左边小于右边,降序排序;
- 代码示例
//自定义类 和 Comparable接口紧密实现
class Person implements Comparable {
String name;
int age;
//重写compareTo方法,实现自定义类的比较规则,返回值0表示相等,返回-1表示降序排序,返回>0表示升序排序
public int compareTo(Object o) {
if (o instanceof Person) {
Person p = (Person)o;
//return (this.age - p.age);//升序
return (p.age - this.age);//降序
}
throw new IllegalArgumentException("非法参数:o=" + o);
}
}
3.3 Comparator比较器 接口<TreeSet排序>
- 概念
Comparator是用于比较两个元素的比较器,实现该接口的类,可以使用该接口特有的方法或比较规则 进行类的比较。 - 使用位置
TreeSet的add()方法底层调用TreeMap的put()方法;TreeMap底层的put()方法的实现采用Comparator作为比较器,用于比较TreeMap中的两个元素。 - 自定义类与Comparator分离
public static void main(String[] args) {
Person p1 = new Person( "张三",20);
Person p3 = new Person( "张三",40);
Person p2 = new Person( "李四",30);
//创建比较器接口,比较两个对象(可能多属性)是否相等,然后排序
Comparator personComparator = new PersonComparator();
//创建set对象,同时初始化set集合的比较器(指定比较器对象)
Set set = new TreeSet(personComparator);
set.add(p1);
set.add(p2);
set.add(p3);
//循环遍历迭代器,每个集合都实现了迭代器接口
for (Iterator iter=set.iterator(); iter.hasNext();) {
Person p = (Person)iter.next();
System.out.println("name=" + p.name + ", age=" + p.age);
}
}
}
class Person {
String name;
int age;
public Person( String name,int age){
this.name = name;
this.age = age;
}
}
//Person实现Comparator比较器,可完成Person类的大小比较
class PersonComparator implements Comparator {
public int compare(Object o1, Object o2) {
if (!(o1 instanceof Person)) {
throw new IllegalArgumentException("非法参数:o1=" + o1);
}
if (!(o2 instanceof Person)) {
throw new IllegalArgumentException("非法参数:o2=" + o2);
}
Person p1 = (Person)o1;
Person p2 = (Person)o2;
return p1.age - p2.age;//根据Person的年龄排序
}
}
四.Iterator接口
- 概念
Iterator 称为迭代接口,实现了Iterator接口的类,表示该类是可以被迭代的。同时Iterable接口中的iterator()方法返回的就是在一个集合元素的迭代器,以证明可以遍历集合中的数据。
迭代:即遍历,可以循环输出集合中的元素。
- 迭代输出:将集合中的元素一个个的使用hasNext()方法进行判断,判断是否有内容,如果有内容就使用next()方法把内容输出。
- 性质特点
Iterator 是一种遍历查询模式,主要可以统一数据结构的访问元素的方式,不用关心各个数据结构 的具体实现。 - 主要方法
- boolean hasNext():判断该集合中是否有元素,如果仍有元素可以迭代,则返回 true;
- Object next():返回可以迭代的下一个元素;
- void remove():利用迭代器 从基础集合中移除迭代返回的最后一个元素,不会改变迭代集合的结构。若在集合的迭代过程中使用集合的remove()方法移除集合元素,会改变当前迭代器的迭代结构。
public static void main(String[] args) {
Collection c = new ArrayList();
//在集合添加元素之前得到的迭代器,迭代集合时会发生异常:ConcurrentModificationException
//Iterator it = c.iterator();
c.add(1);//add加入的是Object类型数据,已使用自动装箱,1已装成Integer
c.add(2);
c.add(3);
//在集合添加元素后得到的迭代器,遍历的集合结构会不一样
Iterator it = c.iterator();
while (it.hasNext()){
it.next();
//c.remove(1);//不能使用集合对象在迭代过程中remove元素,会改变迭代器迭代集合的结构,抛出异常:ConcurrentModificationException
it.remove();//迭代过程中使用迭代器进行remove删除元素不会改变迭代集合的结构
}
}
-
迭代器的执行原理
迭代的实现原理.png
五.Map<图>
- 概念
Map是一个无序、采用键值对的形式存储数据的图。Map中的每一个元素包含一个键对象 和 一个值对象,即Map元素 = 键对象 + 值对象。键对象不允许重复,值对象可以重复<如:身份证号—姓名>。 - 性质特点
- 键值对key-value:在Map中,所有子类都是采用键值对的方式存储元素,和Collection集合毫无关联关系;
- 无序:map中存入元素和取出元素的顺序不相同,put()添加元素的底层实现,采用hash()算法对key进行位置存储处理;
- key键不可重复:所有Map中存储的键key都是无序不可重复的,Map的key和Set集合存储元素的特点相同;
- key-Set转换:Set集合存元素在底层是put到map中的key部分,而map中的key也可以通过keySet()方法返回一个set集合。
- 继承关系
Map无继承父类和实现接口。和Collection同级,但和Collection、Iterator都无关,被HashMap、SortedMap<TreeMap>、HashTable等子类实现。 - 使用特点
- Map的实现类较常用的是HashMap,HashMap对键的存取和HashSet 一样采用哈希算法;
- 如果使用自定义类<引用数据类型>作为 Map 的键对象,自定义类必须重写 equals() 和 hashCode()方法。
-
Map继承结构体系
Map继承结构图.png -
特殊点
Map中使用静态内部类Entry,将map中的键值对关系抽取出来形成set集合中存储的元素关系。 - map遍历
- Set<K> keySet()方法:将所有key抽取出来到一个set集合中,对set集合迭代遍历,再使用get(key)方法获取得到对应的value,该方法将map中key-value的形式变成set中"key=value"的形式;
- Set<Map.Entry<K, V>> entrySet():将所有的key和value全部抽出来到set集合中,而该set集合使用map的内部类map.entry<>作为集合元素类型。对set集合遍历后,使用get(key)和get(value)就可以获取对应的值。
- 常用方法
- map.put(k,v):往map中添加元素,key和value都只能存储引用数据类型-存地址
- map.size():获取Map中存在的键值对数量;
- map.isEmpty():判断map是否为空,底层调用size看键值对数是否为0;
- map.get(key):根据key获取对应的value;
- map.containsKey(key):判断是否包含指定key;
- map.containsValue(value):判断是否包含指定value;
- map.remove(key):根据指定键key删除一个数据;
- map.replace(key,newValue):根据指定key,使用指定的新value替换旧value;
- map.keySet():获取map中所有的key,并将获得key存到set集合中;
- map.clear():清空map中的所有键值对
//面向接口编程,创建一个map对象,并使用泛型指定map中存储的元素类型
Map<Integer,String> map = new HashMap();
//往map中添加元素,key和value都只能存储引用数据类型-存地址
map.put(1,"aaa");
map.put(2,"bbb");
map.put(3,"ccc");
map.put(4,"dddd");
map.put(5,"hahahah");
map.put(5,"dududu");//key不能重复,往相同的key存储value时,会使用后面的value替换前面的value
System.out.println(map.size());
System.out.println(map.get(5));
//获取map中所有的key存到set集合中
Set<Integer> keys = map.keySet();
//遍历Set中的key和value
for (int i = 0;i<map.size();i++){
System.out.println(map.get(i));
}
//for-each遍历
for (Integer key:keys) {
System.out.println(map.get(key));
}
//迭代器遍历
Iterator<Integer> iterator = keys.iterator();
while (iterator.hasNext()){
Integer key = iterator.next();
System.out.println(map.get(key));
}
//将map中所有的key和value抽取出来到set集合中,由(key,value) ---变成---> "key=value"
Set<Map.Entry<Integer, String>> sets = map.entrySet();
//对sets集合for-each遍历,泛型就是元素类型 = Map.Entry<Integer, String>
for (Map.Entry<Integer, String> entry:sets) {
System.out.println(entry.getKey() + "==" + entry.getValue());
}
//迭代器遍历
Iterator<Map.Entry<Integer,String>> iterator1 = sets.iterator();
while (iterator1.hasNext()){
//遍历得到的元素类型就是指定的泛型Map.Entry<Integer,String>
Map.Entry<Integer,String> entry = iterator1.next();
System.out.println(entry.getKey() + "==" + entry.getValue());
}
5.1 哈希表
- 概念
哈希表是一种数据结构,能够提供快速存取操作<通过数组元素的值,可以换算出数据元素的下标,通过下标就可以快速定位数组元素>。 - 性质特点
哈希表是基于数组和哈希算法的,因此存在一旦创建将不能扩展,并且无序(哈希算法的散列特点)。 -
实质
哈希表 = 数组元素的值 + 元素值对应的下标(下标由元素值经过哈希算法得到)
哈希表示例图.png
5.2 HashMap
- 概念
HashMap即Hash+Map,使用哈希算法存储数据的Map<键,值>集合。底层采用哈希表的数据结构存储数据,因此存入元素是无序不可重复的。HashMap的方法是无synchronized修饰的,因此是线程不安全的。 - 静态接口Map.Entry<K,V>
Map.Entry<K,V>是Map中的内部接口,HashMap实现了该内部接口,意为图的条目(所有键值对的个数)。该接口主要存储了Map中所有的key和value,并将该接口作为一个set集合的泛型,相当于将map中所有键值对存到set集合中,方便查询。 -
HashMap实现
HashMap底层图解.png - 字段
- int size:map中键值对的个数;
- int DEFAULT_INITIAL_CAPACITY = 1 << 4:默认初始化容量为16,1 << 4表示 二进制数1左移4为得到二进制数16;
- int MAXIMUM_CAPACITY = 1 << 30:左移30位最大容量;
- float DEFAULT_LOAD_FACTOR = 0.75f:默认加载因子,当HashMap集合底层数组容量达到75%时,Node<>[]数组开始扩容;
- int TREEIFY_THRESHOLD = 8:默认临界值,当数组元素下的单向链表节点数超过8个时,链表变成红黑树;
- int UNTREEIFY_THRESHOLD = 6:取消临界值,当红黑树的节点个数小于6个时,将节点变成单向链表;
- int MIN_TREEIFY_CAPACITY = 64:最小树容量。
- 常用方法
- K getKey():获取map中的key;
- V getValue():获取map中的value;
- String toString() :
- int hashCode() :获取当前map的hashCode()内存地址;
- V setValue(V newValue) :使用新的value替换旧value;
- boolean equals(Object o):判断map中的key是否与指定o相等;
- int hash(Object key):获取指定key的哈希值,即key在数组中的下标;
- map.put(k,v):添加键值对元素;
- v = map.get(k):根据指定key获取对应的value值;
- 遍历Map:先取出key,再根据key获取value;
- 遍历Map:将key和value都取出,直接获取对应的key和value。
- 底层实现
//Node<>实现Map的内部接口,将key和value保存为一个泛型-元素类型
//HashMap底层存储形式Node<>[]的自我实现
static class Node<K,V> implements Map.Entry<K,V> {
//该hash是key调用hashCode()得出哈希值,将哈希值通过哈希算法得到的数组下标
final int hash;// hash == 下标
final K key;//key键
V value;//键对应的value值
Node<K,V> next;//下一个节点(de内存地址)
//内部类构造方法
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//HashMap底层存储元素的形式就是数组,而该Node<>[]数组在HashMap内部已自己实现(如前面显示)
transient Node<K,V>[] table;
//HashMap底层的内部接口,用于实现entrySet()方法
transient Set<Map.Entry<K,V>> entrySet;
}
5.1.1 HashMap与红黑树
- 关系
在HashMap的底层实现中,HashMap使用 Node<>[]数组 + 链表的组合形式进行存储数据的,每个数组元素下挂着一条单向链表。HashMap规定了当链表的节点个数超过8个时,该单向链表变成红黑树;而当红黑树的节点个数少于6个时,该红黑树变成单向链表。 - 原因
当HashMap中存储的元素过多时,不管是Node<>[]还是数组下的链表,都会影响执行效率,因此改变单向链表结构为成红黑树时,可以提高数据的查询检索效率。
5.2 SortedMap
- 概念
SortedMap是一个可以排序的Map集合,实现SortedMap的子类可以完成对key的自动升序排序。
5.2.1 自平衡二叉树
- 概念
自平衡二叉是一种完全二叉树,始终遵循左小右大的原则,即左子树永远小于右子树,左节点数小于右节点数。 -
图解
自平衡二叉树的实现.png - 自平衡二叉树遍历方式
-
先序遍历:根-左-右
先遍历数的根节点root,
再遍历左节点(左节点若有分支也是从根节点开始,然后左节点,到右节点),
再遍历右节点(右节点若有分支也是从根节点开始,然后左节点,到右节点) -
中序遍历:左-根- 右(TreeSet和TreeMap默认中序遍历)
先遍历左子树(若左子树有分支,也是先遍历左节点,到根节点,然后右节点),
再遍历根节点root,
再遍历右子树(若左子树有分支,也是先遍历左节点,到根节点,然后右节点) -
后序遍历:左-右-根
先遍历左子树(若左子树有分支,也是先遍历左节点,到右节点,然后根节点),
再遍历右子树(若左子树有分支,也是先遍历左节点,到右节点,然后根节点),
再到根节点root
5.3TreeMap
- 概念
TreeMap即Tree + Map,TreeMap首先是一颗二叉树,而二叉树中的每一个节点是Map<>类型。TreeMap是可以对 Map中的键key 进行排序的集合。底层采用二叉树的数据结构存储元素。 - 要求
- 基本数据类型或String类型:TreeMap底层可以自动对基本数据类型和String类型的元素进行自动排序,且排为升序。
- 自定义类型:若 map 中的 key 采用的是自定义的引用数据类型,那自定义的引用类需要实现Comaprable 或 Comparator 接口完成排序。
- 字段
- Comparator<? super K> comparator:Comparator比较器,使用于put方法的实现中,完成对元素的排序;
- Entry<K,V> root:二叉树的root根节点;
- int size = 0:二叉树节点个数;
- int modCount = 0:用于统计的变量,初始为0;
- 内部类:在TreeMap的底层实现中,定义了许多静态内部类、成员内部类等,满足底层自我需求。
- 常用方法
- int size():获取TreeMap中二叉树节点的个数;
- boolean containsKey(Object key):判断是否包含指定key的节点;
- boolean containsValue(Object value):判断是否包含指定value的节点;
- V get(Object key):根据指定key返回对应的value值;
- Comparator<? super K> comparator():获取当前TreeMap中元素的比较器;
- K firstKey():获取二叉树中的第一个key;
- K lastKey():获取二叉树中的最后一个key;
- Entry<K,V> getEntry(Object key):
- V put(K key, V value):给指定key替换新的value值,返回旧的value值;
- V remove(Object key):根据指定key删除节点,返回被删除key对应的value值;
- void clear():清楚所有键值对,底层直接将size置0,根节点root置null;
- Object clone():复制一份当前TreeMap对象,可能使用深克隆;
- Map.Entry<K,V> firstEntry():
- Set<K> keySet():获取二叉树中所有节点的key,并将其返回到set集合中;
- Collection<V> values():获取二叉树中所有节点的value,并将其返回到Collection集合中;
- Set<Map.Entry<K,V>> entrySet():获取二叉树中所有节点的key和value,并返回到set集合中;
- V replace(K key, V value):使用新的value值替换指定key的旧value值;
- void forEach():在当前TreeMap上进行for-each增强循环,调用该方法即可循环,不需要手动编写for-each循环。
- 底层部分关键源码实现
//TreeMap底层实现了
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
//无参构造,创建TreeMap对象时,comparator比较器初始化为null
public TreeMap() {
comparator = null;
}
//带参构造,创建TreeMap对象时,初始化comparator比较器对象为comparator的实现类
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//根据指定键key获取二叉树结点
final Entry<K,V> getEntry(Object key) {
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
}
5.4 Hashtable<哈希表、散列表>
- 概念
Hashtable底层采用哈希表的数据结构存储数据,因散列点的特点具有无序性。且Hashtable中的方法都是由synchronized修饰,因此是线程安全的。 - 实现
Hashtable是根据关键码-值<键值对>而直接访问的数据结构,通过把关键码映射到表中一个位置来访问元素。通过hash()算法得到key的下标来读取元素值value。 - 性质特点
哈希表就是将数组 和 链表两者结合的产物,查找容易<数组的特点>,插入删除也很快<单向链表的特点>。
- 数组的特点:查找容易,插入删除困难;
- 链表的特点:查找困难,但是插入删除容易。
-
Hashtable实现原理
Hashtable图解.png - Hashtable实现关键
- hashCode()方法:重写hashCode()方法可以得到key在哈希表数组部分的下标;
- equals()方法:重写equals()方法可以匹配目标key和原链表key是否相等,也因key匹配的不一定就是数组下标的key,可能是数组元素下链表中的key,因此Hashtable和HashMap存入顺序与读取顺序是不一样的。HashSet也是如此。
5.4.1 Properties
- 概念
Properties是继承于Hashtable的一个子类,底层也是采用键值对的形式存储数据,而且存储的键和值只能是 String字符串类型的,加上Properties中所有的方法都是synchronized修饰的,因此Properties也是线程安全的。 - 性质特点
- 线程安全:Properties存储的key和value都只能是String类型的;Properties的方法都是synchronized修饰的
- 常用方法
- String setProperty("key","value"):往Properties中存入数据,存入的key和value只能是String类型;
- String getProperty("key"):从Properties取出数据,取出的key只能是String类型。
六. java.util.Collections 工具类
- 概念
Collections类完全由 在collection上进行操作或返回collection的静态方法组成,是collection功能的扩展类。 - 特点
提供一系列实用的方法,可以完成对collection集合排序,对集合中的内容查找等。 - 常用方法
- 排序方法 Collections.sort(集合对象):对一个集合进行排序,只能对List类型的集合排序;
- 二分查找 int Collections.binarySearch(集合对象, 目标元素):返回一个目标元素的下标;
- 反转字符串 Collections.reverse(集合对象):将一个字符串的顺序反转;
- synchronizedCollection(集合对象):将非线程安全的集合通过外挂将其变成线程安全的。
//创建一个List对象,Collections.sort()中只能对List类型集合排序
List<Integer> list = new ArrayList<>();
list.add(234);
list.add(678);
list.add(856);
list.add(444);
list.add(91);
Collections.sort(list);
for (Integer i:list) {
System.out.println(i);
}
int n = Collections.binarySearch(list,234);//234的下标:n = 1
List<String> l = new ArrayList<>();
l.add("Are you ok");
Collections.reverse(l);
七.泛型<E>
- 概念
在java程序编码中,泛型指的是一些 包含类型参数的类。泛型参数只可以代表类的种类/种型,不能代表个别对象。 - 实质
泛型就是 泛参数类型,属于引用数据类型,泛型 = 集合/数组中元素的类型。 - 作用特点
- 泛型就是元素的类型,泛型限定了集合的元素类型,能更早的发现错误。如ClassCastException 类型转换异常,jvm通常在运行期才会现;如果使用泛型,jvm在编译期就会发现错误。
- 发现错误越早,越容易调试,越容易减少成本;
- 泛型定义后,该泛型的类型集合中 不能存储与泛型不同的参数数据;
- 泛型实现功能与 instanceOf字符类似,使用泛型后,可以不用进行强制转换。
7.1 泛型的类型
- 类-泛型
使用类泛型,可以指定方法的返回结果是自定义类的泛型,而不是一般的Object类型。使用字母T表示类泛型,T表示所有类型的公共高级接口,包括原始类型、参数化类型、数组类型、类型变量和基本类型等。
class My<T>{
public T doMy(){
return null;
}
}
- 方法参数-泛型
使用方法形参泛型,可以指定方法的参数类型。
public class AutoGeneric<autoString> {
//基本类型参数
public void dosome(int i){
System.out.println(i);
}
//泛型类型的参数
public void domore(autoString str){
System.out.println(str);
}
}
7.2 自定义泛型
- 概念
使用自定义的 引用数据类型(即自定义类)作为泛型,限定集合中只能存储自定义类类型的元素,从而满足实际的开发需求。 - 特点
通常情况下,自定义泛型一般使用 T 和 E 表示。
- T:type,表示所有类型的公共高级接口。它们包括原始类型、参数化类型、数组类型、类型变量和基本类型;
- E:element,表示一个程序元素,如包、类、方法;
- 作用
使用泛型可以指定自定义泛型类中方法的参数类型、方法的返回结果类型都是泛型;不使用泛型时,方法的返回结果类型通常都是Object类型。
class My<T>{
public T doMy(){
return null;
}
}
class AutoGeneric<autoString> {
public void dosome(int i){
System.out.println(i);
}
public void domore(autoString str){
System.out.println(str);
}
public static void main(String[] args) {
//使用泛型创建对象
AutoGeneric<String> ag = new AutoGeneric<>();
ag.domore("autoString type");//IDEA提示参数类型是autoString泛型
ag.dosome(23);//IDEA提示参数类型是int类型
//不使用泛型创建对象
AutoGeneric aug = new AutoGeneric();
aug.domore("Object type");//提示参数类型是Object类型
ag.dosome(88);//提示参数类型是int类型
My m = new My();
m.doMy();//调用方法时,IDEA提示返回的结果是Object类型
My<Integer> my = new My<Integer>();
my.doMy();//调用方法时,IDEA提示返回的结果是Integer类型
}
}
7.3 自动类型推断机制
- 概念
自动类型推断机制又称钻石表达式。在集合的泛型中,jvm支持自动类型推断,当子类型集合没有写明泛型时,可自动根据父类型的泛型推断出子类型集合的元素类型。 - 示例
public static void main(String[] args) {
// ArrayList<此泛型类型自动推断>(),JDK8之后才允许
List<Animal> myList = new ArrayList<>();
//List<> list1 = new ArrayList<Animal>();//支持父类型泛型自动推断出子类型,不支持子类型泛
myList.add(new Animal());
myList.add(new Cat());
myList.add(new Bird());
// 遍历
Iterator<Animal> it = myList.iterator();
while(it.hasNext()){
Animal a = it.next();
a.move();
}
List<String> strList = new ArrayList<>();
/*类型不匹配
strList.add(new Cat());
strList.add(123);
*/
//自动类型推断参数类型为String
strList.add("http://www.126.com");
}
7.4 for-each循环增强遍历机制
- 优缺点
- 优点:语法格式简洁,对于集合或数组可以快速遍历
- 缺点:遍历时无下标,因此在使用下标遍历的需求中不合适
- 示例
public static void main(String[] args) {
// 创建List集合
List<String> strList = new ArrayList<>();
// 添加元素
strList.add("hello");
strList.add("world!");
strList.add("kitty!");
// 遍历,使用迭代器方式
Iterator<String> it = strList.iterator();
while(it.hasNext()){
String s = it.next();
System.out.println(s);
}
// 使用下标方式(只针对于有下标的集合)
for(int i = 0; i < strList.size(); i++){
System.out.println(strList.get(i));
}
// 使用foreach
for(String s : strList){ //泛型使用的是String类型,所以返回也是String
System.out.println(s);
}
}
常见面试题
- 为什么重写hashCode()方法的同时需要重写equals()方法?
答:
- 因为在Map中,数据是以键值对的形式存在的。
- 而在Hashtable中,Hashtable底层是使用Node<>[ ]数组+链表的组合形式存储数据的,数组的同一个下标之下有一条单向链表。
- 重写hashCode()只能得到key在数组中的下标,但是并未能确定key在链表的具体位置,也不能确定key是否之前已经存在。
- 因此还需要重写equals()方法,可以更加确定key的位置,并且判断key是否已存在。
- 同一个数组下有一条链表,链表中存储了多个不同的key,因此hashCode相同只能得到相同的key数组下标,不能判断key对应的value就一定相等。
- 重写的hashCode()方法也因此不能只返回一个固定值。
这么多的集合中,你用哪个集合最多?
答:ArrayList集合。
因为往数组添加元素,实则在它的末尾添加元素,效率不受影响。另外,我们在实际运用中,搜索和查找某个元素的操作比较多,数组查找元素的效率高。
检索效率比较高(每个元素占用空间大小相同,数组的内存地址是连续的,知道首元素内存地址,知道下标,通过数学表达式计算出元素的内存地址,所以检索效率最高)。使用集合模拟单向链表的实现?
答:单向链表的特点,以节点为基础单元,每个节点包含数据部分+指向下一个节点的地址组成。可以将节点当作一个对象,而链表就是由多个节点组成。
//节点类
public class Node {
int data;//节点的数据
Node next = null;//指向下一节点的内存地址,起初都为空
public Node() {
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
public Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
//链表
public class Link {
private Node head = null;//链表头节点,初始为空
private int size;//链表长度
//创建节点
public Link() {
}
public Link(Node head) {
this.head = head;
}
public int size(){
size = 0;//链表初始长度为0
Node currentNode;//创建新节点-指向当前节点
currentNode = head;//size=0时,头节点为当前节点
while (currentNode != null){
size++;//
currentNode = currentNode.next;//将下一个节点的内存地址赋给当前节点保存
}
return size;
}
//添加节点:找到链表的末尾节点,把新的数据节点添加在后面
public void addNode(int data){
//创建要添加的节点对象
Node newnode = new Node(data);
if (head == null) { //判断头结点是否为空--遍历从头到尾
head = newnode;//头节点为空,直接保存新节点
return;
} else {
/*
Node currentNode = head;
currentNode.next = newnode;//将要添加的节点作为下一个节点
*/
Node currentNode = head;
while (currentNode.next != null) { //找到下一个节点直至末尾
currentNode = currentNode.next;//将下一个节点的内存地址赋给当前节点
}
currentNode.next = newnode;//将要添加的节点作为下一个节点
}
}
//删除节点:根据下标找到相应的节点,将删除节点的前一节点 指向 删除节点的下一节点
//由 前-> 删除-> 后 ===变成===> 前-> 后
public boolean deleteNode(int index){
if (index < 1 || index > size()) {
System.out.println("删除的元素下标超出范围");
return false;
}
if (index == 1) {
head = head.next;
return true;
}
Node pre_node = head;//前节点
Node cur_node = pre_node.next;//要删除的节点
int i = 2;//
while (pre_node != null) {
if (i == index) {
pre_node.next = cur_node.next;//删除当前节点,将删除节点的下一个节点内存地址 赋给 前一节点
return true;
} else {//向下遍历链表
pre_node = pre_node.next;
cur_node = cur_node.next;
i++;
}
}
return true;
}
//查询节点,根据数据data查找节点,返回节点的下标
public int selectNode(int data){
Node node = head;//从头开始遍历链表
int index = 0;//从下标0开始遍历链表
while (node != null){
if (node.data == data){
return index;
}
node = node.next;//遍历下一个节点
index++;
}
return -1;//
}
//修改节点
public boolean updateNode(int Index,int data){
Node node = head;//从头开始遍历链表
int index = 0;
while (node != null){
if(index == Index){
node.data = data;
return true;
}
node = node.next;//遍历下一个节点
index++;
}
return false;
}
//遍历输出节点
public void printLink() {
Node node = head;//从头开始遍历链表
while (node != null) {
System.out.print(node.getData() + " ");
node = node.next;//遍历下一个节点
}
System.out.println();
}
}
//测试
简单描述一下泛型机制?
答:讲述以下HashMap和Hashtable的区别?
答:
- HashMap:底层是哈希表的数据结构,采用数组存储元素。HashMap的方法无synchronized修饰,是非线程安全的;HashMap允许存入的key或value都为null;HashMap初始化容量为16,扩容的容量为原来的两倍(超过75%就扩容);
- Hashtable:底层是哈希表的数据结构,采用数组存储元素。Hashtable的方法采用synchronized修饰,是线程安全的;Hashtable不允许存入的key或value任何一个为null,Hashtable在使用put()方法存入元素时,底层都调用了equals()方法判断存入的值是否为空;Hashtable初始化容量为11,扩容的容量为原来的两倍+1。
- Comparator 和 Comparable 的区别?
答:
- Comparable是默认的比较接口,Comparable 和需要比较的对象紧密结合到一起;
- Comparator 可以分离比较规则,更具灵活性。
一个类实现了 Camparable 接口则表明这个 类的对象 之间是可以相互比较的,这个类对象组成的集合也就可以直接使用 sort 方法排序。
Comparator 可以看成一种算法的实现,将算法和数据分离<对象 和 对象的比较实现>
请使用两种方法完成从一个数组中查找得到一个目标数据,并讲明原理。
冒泡排序
选择排序说一下数组和链表的认识,查询效率更高的是哪个?修改删除效率更高的是哪个?说明原因。
答:
第一:空间存储上,内存地址是连续的。
第二:每个元素占用的空间大小相同。
第三:知道首元素的内存地址。
第四:通过下标可以计算出偏移量。
通过一个数学表达式,就可以快速计算出某个下标位置上元素的内存址,直接通过内存地址定位,效率非常高。
优点:检索效率高。
缺点:随机增删效率较低,数组无法存储大数据量。
注意:数组最后一个元素的增删效率不受影响。