2.2:链式存储结构

为了表示每个数据元素和其后面的元素之间的逻辑关系。对数据元素ai来说,除了要存储其本身的信息外,还需要存储一个指示其直接后继的信息。我们把存储这个数据元素的域称为数据域,存储直接后继位置的域称为指针域。这两部分信息称为节点
node。

N个节点链接为一个链表,这个就是线性表的链式存储结构。因此,每个节点中只包含了一个指针域,所以叫做单链表。

一般会在第一个数据节点的前面附加一个节点,叫做头节点。

头指针是链表指向第一个结点的指针,若链表有头节点,则是指向头节点的指针。

有了头节点,对在第一个元素节点前插入节点和删除节点就与其他操作节点统一了。

可以没有头节点,但是一定有头指针。

.2.1:单链表的插入和删除

插入:空节点S s.next=p.next   p.next=s;

删除 要删除的q q=p.next   p.next=q.next

单链表的插入和删除其实分为2个部分:

1:遍历和查找 节点i

2:插入和删除节点i

从整个算法的时间复杂度来说,其实都是O(n)操作。但是侧重点不一样。链表的插入和删除都是O(n),主要是由于在查找结点的时候消耗掉了,再进行插入和删除的时候,是O(1).但是顺序表的查找要操作的节点位置是O(1),但是在进行插入和删除的时候是O(n)。需要把相关数据元素整体移动!!!在移动的过程中消耗的是O(n)。

2.2.2 单循环链表和双向链表

循环链表:将单链表中的最后一个节点的指针改为指向头节点,就使整个单链表形成了一个环,这种首尾相互循环的单链表就成为单循环链表。

双向链表:在单链表的每个节点中,再设置一个指向其前驱的指针域。

双向链表的添加: p  q中添加S

首先保证P和Q 之间是没有断线

1:S.prior=P

2: S.next=P.next

3:     p.next.prior=s

4:   p.next=s

顺序非常重要,如果第4步先执行,那么p的后继指针节点位置就会消失,也就是说p和q之间就会断线

双向链表的删除:删除S节点

1:把S.next赋值给S的前驱的后继  S.prior.next=s.next

2:把S。prior 赋值给S.next.prior    s.next.prior=s.prior

        昨天又看了下《Java核心技术》第二卷讲集合类这里,上来说说。
       
ArrayList和LinkedList,这是Java中的动态数组和链表。动态数组其实比较简单,就是一个长度可以根据实际情况改变的数组。我们如果要查找某一个动态数组中的元素,可以通过get()方法来查找,只要知道该元素下标就可以了。
       
而LinkedList,也就是链表,这个与我们所知道的一般链表稍有不同。一般的链表元素中,除了放这个结点的数据外,还指向下一个结点。一个指向下一个,就这样构成了链表。但是Java中的链表,除了放本来的数据和指向下一个结点外,还指向上一个结点。因此,Java中的LinkedList是双向的。那么有什么用呢?还有就是ArrayList和LinkedList有什么区别?
       
这个就要从查找元素的效率和添加删除元素的效率来讲了。在动态数组中,如果我们要在某一个位置添加或者删除一个元素,剩下的每个元素都要相应地往前或往后移动。如果该动态数组中的元素很多,那么,每当我们添加或删除一个元素后,需要移动的元素就非常多,因此,效率就比较低。但是,如果我们使用LinkedList就不一样了。如果我们要在某一个位置添加一个元素,例如,要在A,
C之间插入B。本来A是指向C,C也指向A的。现在,只需要将B放到A和C之间,同时让B向前指向A,向后指向C,并且让A从C指向B,让C从A指向B就可以了。如果该链表中元素非常多,我们只需做这个操作就可以了,并不需要移动剩下的元素。所以说LinkedList在添加和删除元素上的效率要比ArrayList高很多。而且,Java中有一个叫ListIterator的迭代器。该迭代器不仅可以向后迭代元素,还能向前迭代,而且还有add()来在某一位置添加元素,十分方便。不过说到查找效率的话就反过来了,是ArrayList的效率比LinkedList的效率高,因为你只要提供元素的下标即可。如果你不知道如何选择ArrayList和LinkedList,就从这两个方面来考虑就行了。
       
关于哈希表,该书有一个错误。事实上,Hash表为每个对象计算出一个整数,称为Hash
Code(哈希码)。Hash表是个链接式列表的阵列。每个列表称为一个buckets(哈希表元)。对象位置的计算 index
= HashCode % buckets (HashCode为对象哈希码,buckets为哈希表元总数)。
这里,书上说先求出index,然后再用对象的哈希码减去这个index就是对象在哈希表中的索引。应该是不要减去的,而且它后面举的例子也没有减去,估计是印刷错误。
        这里转贴一下关于哈希查找的定义: 哈希查找(hashing
search)是一种完全不同的查找方法,它不是通过比较确定待查元素的位置,而是在元素的存储位置和它的关键字K之间建立一个对应关系H,使每个关键字K与结构中的一个位置相对应。因而在查找时,只要根据这个对应关系H找到关键字K的存储位置H(K),若结构中存在关键字和K相等的记录,则必定在H(K)
这个存储位置上,因此不需要比较就可直接取得所查记录。称这个对应关系H为哈希函数,H(K)的值为哈希地址或散列地址,按这个思想建立的表为哈希表。
       
但实际情况是,对不同的关键字可能根据哈希函数得到相同的地址值,即有:K1≠K2,而H(K1)=H(K2),这种现象称为冲突,具有相同函数值的不同关键字称为同义词。所以在构造哈希表时还应该为发生冲突的关键字另找存储空间。这一过程称为处理冲突的过程。
       
上面是关于哈希表的一些介绍。解决冲突的一种常用方法就是链地址法,链地址法处理冲突的方法是:将所有关键字为同义词的数据元素存储在同一链表中。例如,某个对象的哈希码是7,而哈希表元为3,那么7%3=1,因此,该对象就放在哈希表元为1的链表中。如果该表上已经有一个对象了,那么就接着这个对象放在后面就行了。

1:算法时间复杂度

澳门新葡亰游戏网址,2:算法的空间复杂度

计算方法:只保留最高阶。用常数1代替

大O表示法:语句的总执行次数
T(n)是关于问题规模n的函数。随着问题规模的增加,算法时间的增长率和f(n)的增长率相同。记作T(n)=O(f(n))。

常用的算法时间复杂度:

5 Map

Map是保存了Key—Value的键值对。其中它的key是一个set集合,value是一个collections。

主要有下面几种map。一个是HashMap一个是TreeMap  还有一个HashTable。

5.1 HashMap

容量(Capacity)和负载因子(Load factor)

默认容器是16,加载因子是0.75,当bucket填充的数目(即hashmap中元素的个数)大于capacity*load
factor时就需要调整buckets的数目为当前的2倍并且重新调用Hash方法。

HashMap是线程不安全的。在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。

5.2 HashTable

它是线程安全的,它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table,这就意味着所有的线程都在竞争一把锁,在多线程的环境下,它是安全的,但是无疑是效率低下的。

5.3 ConcurrentHashMap

ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成。

Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁,也就是上面的提到的锁分离技术,而每一个Segment元素存储的是HashEntry数组+链表,这个和HashMap的数据存储结构一样。

在Jdk1.8的时候,已经完全修改了。

JDK1.8的实现已经摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap。

对数阶:count=count*2  count< n 有多少个2相乘后大于n,就会退出

4:集合

集合和数组的区别:

1:数组就是一个顺序表,内容是固定的,是用一段连续的存储单元来表示

而集合容量是不固定的。有个默认值为10,当超过的时候,会进行扩容,一般是扩容1.5倍

2:数组可以存放基本数据类型和引用类型,但是一个数组里面只能存放一种类型

而集合,可以保持有多种数据类型。

在现实生活中,不同的事物需要使用不同的容器存放,这样不断抽取,就出现了一个顶级接口collection.

Collection没有直接的实现类,一般都是实现它的子类。并且一般都是以多态的形式出现。

使用多态,前提是,引用类型和实际的对象的类型之间需要有继承关系(实现接口的关系)

4.1:迭代器

迭代器iterator  是一个标准化来遍历集合数据的接口。

但是要遍历集合中的所有元素,因为集合的实现不同,保存数据的方式也不一样,所以我们取出数据的方法也不一样;

要该集合内部实现了迭代器,就可以在不知道API或者集合内部结构的情况下通过迭代器遍历该集合的元素。

迭代器存在一个快速失败机制,Java
集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作或者集合在迭代元素时直接直接调用自身方法改变集合结构而没有通知迭代器时,有可能会触发
fail-fast 机制并抛出ConcurrentModificationException异常

因为一旦获取这个容器的迭代器对象,那么这个迭代器就会保存这个容器的索引信息,

每次调用迭代器的next方法的时候,就会移动光标,就会比对迭代器的信息和元素信息,如果两者不相等,就会报错,建立多线程下使用CopyOnWriteArrayList
(线程安全的集合类)。

迭代器只能单向迭代。

使用集合的remove会报错,但是使用迭代器的remove不会报错!!!!

4.2:list接口

使用增强for循环遍历list的时候,不能修改容器接口,会报错,

List接口的实现类主要有ArrayList;LinledList;Vector;

这个容器允许有重复元素,也可以存储null。

ArrayList
底层,实际上是用一个Object数组来保存数据的默认大小是10.当容量不够的时候,会开启自动扩容,扩容为1.5倍。调用方法是Arrays.copyOf来实现扩容。

LinkedList 其实就是基于链表的接口实现。

Vector 其实就是一个线程安全的list,效率比较低。

4.3 Set接口

1、set接口,只能保存不重复的元素;判断是否重复,主要通过equals方法判断;读取数据的顺序是无法保证的。

常用的HashSet TreeSet等

Hash表:

利用哈希算法,根据数据的特征,对保存的数据进行分块的一种数据结构,可以提高数据的查找效率。

Hash表就是一个链表+数组。

Hash保存数据的流程:

1、计算要保存对象的哈希值(Java中通过对象的hashCode方法获取),然后根据哈希值计算数据在哈希表中的位置;

2、找到位置后,如果位置上已经有数据了,就调用equals方法判断新保存的数据和原来的数据是否相等,如果相等,就不用保存,否则就在相应位置扩展一个空间保存新数据;

HashSet要能够保证保存的对象唯一,首先需要调用保存的对象的hashCode方法,获取哈希值,计算对象需要保存的位置,并以此判断对象接下来是否需要通过equals方法进行相等性判断;

如果两个对象的哈希值不同,就不会保存在同一区域,也不会调用equals方法进行相等性验证

如果是自定义的对象保存到HashSet中时,需要重写HashCode方法和Equal方法

LinkedHashSet  这个就是为了保证存储有顺序。

4.3.2 TreeSet

如果向集合中存储自定义元素,并且还按照一定字段进行排序。需要使用TreeSet。底层是二叉树的实现,

在排序时通过compareTo(或 compare)方法对所有元素进行比较;

自定义的对象必须实现Compareable接口或者是直接传递比较器来进行比较。

4.4:总结

Collection集合:它本身接口,是在定义所有单列集合的共性操作规则。增 删
查  判断  遍历方法,没有修改的方法

List接口:

   
有序列表,可以存放重复元素,可以根据下标(索引、角标)操作集合中的任何元素。

    List接口中定义了可以根据角标操作的增删改查方法。

    ArrayList:底层是可变数组,查询快,增删慢。线程不安全。

    LinkedList:底层是链表结构,增删快,查询慢。线程不安全。

    Vector:底层是可变数组,什么都慢。被ArrayList代替。线程安全。

Set接口:

    不能存储重复元素。允许有一个null。

   
HashSet:底层哈希表,不保证存取顺序。保证元素唯一,需要依赖元素的hashCode和equals方法。因此给哈希表中存放的元素需要复写Object类中的hashCode和equals方法。

          
LinkedHashSet:底层是哈希表+链表,没有自己特有方法,全部继承HashSet,可以保证存取顺序。保证唯一。

   
TreeSet:底层是二叉树(红黑树)。可以对其中存储的元素进行排序。排序依赖当前这个对象的compareTo方法。要求给二叉树中存储的对象所属的类要实现Comparable接口。

   
如果对象自身的compareTo方法不符合当前要求,或者对象本身就没有比较大小的方法,这时可以定义比较器对象Comparator。将这个比较器传递给TreeSet集合。

网站地图xml地图