疯狂的小鸡

数据结构-表

字数统计: 2k阅读时长: 6 min
2018/10/22 Share

散列表

散列表是普通数组概念的推广。由于对普通数组可以直接寻址,使得能在O(1)时间内访问数组中的任意位置。在散列表中,不是直接把关键字作为数组的下标,而是根据关键字计算出相应的下标。

散列算法

使用散列的查找算法分为两步。第一步是用散列函数将被查找的键转化为数组的一个索引。我们需要面对两个或多个键都会散列到相同的索引值的情况。因此,第二步就是一个处理碰撞冲突的过程,由两种经典解决碰撞的方法:拉链法和线性探测法。

散列表是算法在时间和空间上作出权衡的经典例子

  • 如果没有内存限制,我们可以直接将键作为(可能是一个超大的)数组的索引,那么所有查找操作只需要访问内存一次即可完成。但这种情况不会经常出现,因此当键很多时需要的内存太大。

  • 另一方面,如果没有时间限制,我们可以使用无序数组并进行顺序查找,这样就只需要很少的内存。而散列表则使用了适度的空间和时间并在这两个极端之间找到了一种平衡。

散列函数

我们面对的第一个问题就是散列函数的计算,这个过程会将键转化为数组的索引。我们要找的散列函数应该易于计算并且能够均匀分布所有的键。

散列函数和键的类型有关,对于每种类型的键我们都需要一个与之对应的散列函数。

正整数
将整数散列最常用的方法就是除留余数法。我们选择大小为素数M的数组,对于任意正整数k,计算k除以M的余数。(如果M不是素数,我们可能无法利用键中包含的所有信息,这可能导致我们无法均匀地散列值。)

浮点数
将键表示为二进制数,然后再使用除留余数法。(让浮点数的各个位都起作用)(Java就是这么做的)

字符串
除留余数法也可以处理较长的键,例如字符串,我们只需将它们当做大整数即可。即相当于将字符串当做一个N位的R进制值,将它除以M并取余。

软缓存
如果散列值的计算很耗时,那么我们或许可以将每个键的散列值缓存起来,即在每个键中使用一个hash变量来保存它的hashCode()返回值。

碰撞处理

一个散列函数能够将键转化为数组索引。散列算法的第二步是碰撞处理,也就是处理两个或多个键的散列值相同的情况。

拉链法:将大小为M的数组中的每个元素指向一条链表,链表中的每个结点都存储了散列值为该元素的索引的键值对。
查找分两步:首先根据散列值找到对应的链表,然后沿着链表顺序查找相应的键。
拉链法在实际情况中很有用,因为每条链表确实都大约含有N/M个键值对。
基于拉链法的散列表的实现简单。在键的顺序并不重要的应用中,它可能是最快的(也是使用最广泛的)符号表实现。

实现散列表的另一种方式就是用大小为M的数组保存N个键值对,其中M>N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为开放地址散列表。
开放地址散列表中最简单的方法叫做线性探测法:当碰撞发生时,我们直接检查散列表中的下一个位置(将索引值加1),如果不同则继续查找,直到找到该键或遇到一个空元素。

栈和队列

概念很简单,栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构,而队列(Queue)则是一种先进先出 (fisrt in first out,FIFO)的结构,如下图:
栈和队列

java中栈和队列的实现

java中的stack类是Vector的一个子类,它实现了一个标准的后进先出的栈。堆栈只定义了默认构造函数,用来创建一个空栈。 堆栈除了包括由Vector定义的所有方法,也定义了自己的一些方法。

  • boolean empty() 测试堆栈是否为空。
  • Object peek( ) 查看堆栈顶部的对象,但不从堆栈中移除它。
  • Object pop( ) 移除堆栈顶部的对象,并作为此函数的值返回该对象。
  • Object push(Object element) 把项压入堆栈顶部。
  • int search(Object element) 返回对象在堆栈中的位置,以 1 为基数。

Queue接口与List、Set同一级别,都是继承了Collection接口。

没有实现的阻塞接口的:

  • LinkedList实现了java.util.Queue接口和java.util.AbstractQueue接口。

  • PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序(通过其 java.util.Comparable 实现)或者根据传递给构造函数的 java.util.Comparator 实现来定位。

  • ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们,所以只要不需要知道队列的大 小,ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢,需要遍历队列。

实现阻塞接口的:
java.util.concurrent 中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素,线程执行操作阻塞,直到有空间或者元素可用。具体可见多线程-java.util.Concurrent

栈和队列的应用

Stack这种数据结构用途很广泛,比如编译器中的词法分析器、Java虚拟机、软件中的撤销操作、浏览器中的回退操作,编译器中的函数调用实现等等。

Stack使用的一个最经典的例子就是算术表达式的求值了,这其中还包括前缀表达式和后缀表达式的求值。E. W. Dijkstra发明了使用两个Stack,一个保存操作值,一个保存操作符的方法来实现表达式的求值。

有一个场景是利用stack 处理多余无效的请求,比如用户长按键盘,或者在很短的时间内连续按某一个功能键,我们需要过滤到这些无效的请求。一个通常的做法是将所有的请求都压入到堆中,然后要处理的时候Pop出来一个,这个就是最新的一次请求。

Queue的应用也很广泛,最广泛的就是排队了,”先来后到” First come first service ,以及Queue这个单词就有排队的意思。

比如我们的播放器上的播放列表,我们的数据流对象,异步的数据传输结构(文件IO,管道通讯,套接字等)。

还有一些解决对共享资源的冲突访问,比如打印机的打印队列等。消息队列等。交通状况模拟,呼叫中心用户等待的时间的模拟等等。

CATALOG
  1. 1. 散列表
    1. 1.1. 散列算法
    2. 1.2. 散列函数
    3. 1.3. 碰撞处理
  2. 2. 栈和队列
    1. 2.1. java中栈和队列的实现
    2. 2.2. 栈和队列的应用