1. Set 与 BitSet
Set(集合)是没有重复的对象集合,所有的元素都是唯一的。
Set(集合)分为可变的和不可变的集合。默认情况下,Scala 使用的是不可变集合,如果要使用可变集合,需要引用 scala.collection.mutable.Set 包。
BitSet(collection.immutable.BitSet)和Set类似,但操作更快。
BitSet代表一个由小整数构成的容器,这些小整数的值表示了一个大整数被置1的各个位。比如说,一个包含3、2和0的bit集合可以用来表示二进制数1101和十进制数13.
BitSet内部的使用了一个64位long型的数组。数组中的第一个long表示整数0到63,第二个表示64到27,以此类推。所以只要集合中最大的整数在千以内BitSet的压缩率都是相当高的。
BitSet操作的运行时间是非常快的。查找测试仅仅需要固定时间。向集合内增加一个项所需时间同BitSet数组中long型的个数成正比,但这也通常是个非常小的值。
1.1 Set 初始化
// 定义不可变 set
val set1 = Set(1,2,3,4,5)
println(set1) // Set(5, 1, 2, 3, 4)
// 定义可变 set
import scala.collection.mutable
val set2 = mutable.Set(1,3,9,6,14,5,2,1)
println(set2) // Set(9, 1, 5, 2, 6, 3, 14)
//创建一个空的可变Set
val words = mutable.Set.empty[String] //(words.toString returns Set())
// 定义不可变 bitSet
val bitSet1 = collection.immutable.BitSet(1,2,3,3,2,1)
println(bitSet1) //BitSet(1, 2, 3)
// 定义可变 bitSet
val bitSet2 = collection.mutable.BitSet(1,2,3,3,2,1)
println(bitSet2) //BitSet(1, 2, 3)
1.2 Set 查看元素
// 定义不可变 set
val set1 = Set(1, 2, 3, 4, 5)
println(set1) // Set(5, 1, 2, 3, 4)
println(set1.size)//长度 5
println(set1.head)//头元素 5
println(set1.last)//尾元素 4
println(set1.sum)//求和 15
println(set1.max)//最大值 5
println(set1.min)//最小值 1
// 查找set中是否包含某元素
println(set1(3)) // true, 集合中有元素3
println(set1(0)) // false, 集合中没有元素0
1.3 Set 增加元素
import scala.collection.mutable
val set1 = mutable.Set(1,2,3)
set1 += 4 // Set(1)
println(set1) //Set(1, 2, 3, 4)
set1 += (5,6) // Set(1,3,2,4)
println(set1) //Set(1, 5, 2, 6, 3, 4)
// ++= 符号后面只能跟数组集合
val set2 = set1 ++ Set(7,8)
println(set2) //Set(1, 5, 2, 6, 3, 7, 4, 8)
//add 方法添加时只能添加单个元素
set1.add(9)
println(set1) //Set(9, 1, 5, 2, 6, 3, 4)
// ++ 运算符并没有将原有set集合改变 只是3将两个set集合进行合并形成新的set集合
val set3 = mutable.Set(1,2,3)
val set4 = set3 ++ Set(2,3,4)
println(set4) //Set(1, 2, 3, 4)
// 同
val set5 = Set(1,2,3) ++ Set(2,3,4) // Set(1, 2, 3, 4)
println(set5) //Set(1, 2, 3, 4)
println("123")
val bitSet1 = collection.mutable.BitSet()
bitSet1 += (1,3,5)
println(bitSet1) // BitSet(1, 5, 3)
bitSet1 ++= Set(7,9)
println(bitSet1) // BitSet(1, 3, 5, 7, 9)
1.4 Set 删除元素
import scala.collection.mutable
val set1 = mutable.Set(1,2,3,4,5,6,7)
// 删除元素
val set2 = set1 - 1
println(set2) // Set(5, 2, 6, 3, 7, 4)
val set3 = set2 - (3,2)
println(set3) // Set(5, 6, 7, 4)
val set4 = set3 --= Set(4,5)
println(set4) // Set(6, 7)
//全部删除
set4.empty
println(set4) // Set()
val set5 = Set(1,2,3) -- Set(2,3,4)
println(set5) // Set(1)
1.5 set 交并补集
val set1 = Set(1,2,3,4)
val set2 = Set(3,4,5,6)
// 计算交集
val set3 = set1 & set2
println(set3) //Set(3, 4)
// 同
val set4 = set1.intersect(set2)
println(set4) //Set(3, 4)
// 计算并集
val set5 = set1 | set2
println(set5) //Set(5, 1, 6, 2, 3, 4)
// 同
val set6 = set1 union set2
println(set6) //Set(5, 1, 6, 2, 3, 4)
// 计算补集
val set7 = set1 &~ set2
println(set7) //Set(1, 2)
// 同
val set8 = set1 diff set2
println(set8) //Set(1, 2)
2. Tuple (元组)
Tuple是一个可以容纳不同类型元素的类。
Tuple是不可变的(长度固定,元素不可变),常用于有多个返回值的函数,或者多个变量的同时定义。
Tuple使用括号来表示”()”,获取元组中的值使用下划线表示,下标从1开始
2.1 Tuple 初始化
//定义一个元组
val t1 = ("小明", "男", 18)
println(t1) //(小明,男,18)
println(t1.getClass()) //class scala.Tuple3
println(t1._1) //小明
println(t1._2) //男
println(t1._3) //18
//只有两个元素的元组,被称之为对偶元组
val t2 = ("id",123) //对偶元组 (key-value)
println(t2._1) //id
println(t2._2) //123
//还可以将元组的元素单独赋值给对应的变量
val tuple3,(name,age,sex)=("小明",18,"男")
println(name) //小明
println(age) //18
println(sex) //男
2.7 Tuple 其他操作
val numPairs = List((2, 5), (3, -7), (20, 56))
// 遍历元组
for ((a, b) <- numPairs) {
println(a * b)
}
/**
* 10
* -21
* 1120
*/
3. Vector(向量)
Vector类型的构建和修改与其他的序列结构基本一样。
对于只需要处理数据结构头结点的算法来说,List非常高效。可是相对于访问、添加和删除List头结点只需要固定时间,访问和修改头结点之后元素所需要的时间则是与List深度线性相关的。
Vector(向量)是用来解决list不能高效的随机访问的一种结构。Vector结构能够在“更高效”的固定时间内访问到列表中的任意元素。虽然这个时间会比访问头结点或者访问某数组元素所需的时间长一些,但至少这个时间也是个常量。因此,使用Vector的算法不必仅是小心的处理数据结构的头结点。由于可以快速修改和访问任意位置的元素,所以对Vector结构做写操作很方便。
Vector结构通常被表示成具有高分支因子的树(树或者图的分支因子是指数据结构中每个节点的子节点数目)。每一个树节点包含最多32个vector元素或者至多32个子树节点。包含最多32个元素的vector可以表示为一个单一节点,而一个间接引用则可以用来表示一个包含至多32*32=1024个元素的vector。从树的根节点经过两跳到达叶节点足够存下有2的15次方个元素的vector结构,经过3跳可以存2的20次方个,4跳2的25次方个,5跳2的30次方个。所以对于一般大小的vector数据结构,一般经过至多5次数组访问就可以访问到指定的元素。这也就是我们之前所提及的随机数据访问时“运行时间的相对高效”。
3.1 Vector 初始化
val v1 = scala.collection.immutable.Vector.empty
println(v1) //Vector()
val v2 = collection.immutable.IndexedSeq(1, 2, 3)
println(v2) //Vector(1, 2, 3)
val v3 = Vector(1,2,3,4,5)
println(v3) //Vector(1, 2, 3, 4, 5)
val v4 = Vector(1 to 3:_*)
println(v4) //Vector(1, 2, 3)
3.2 Vector 查看元素
val v1 = Vector(1,2,3,4,5)
// 取出下标为0 的元素
println(v1(0)) // 1
// 取出前两个元素
println(v1.take(2)) //Vector(1, 2)
//在某类型的集合对象上调用view方法,得到相同类型的集合,但所有的transform函数都是lazy的,从该view返回调用force方法。
println(v1.max)
println(v1.min)
v1.map(v => {
println(v) //1,2,3,4,5
})
// 同
v1.map(println(_)) //1,2,3,4,5
// 查看Array 长度
println(v1.length) //5
println(v1.size) //5
3.3 Vector 增加元素
Vector 是不可变的,不能增加长度,可以将元素追加生成一个新的Vector
// 定义一个Vector
val v1 = Vector(1,2)
println(v1) //Vector()
// 单个元素追加,在尾部追加元素并生成一个新的Vector
val v2 = v1 :+ 3 :+ 4
println(v2) //Vector(1, 2)
println(v2.getClass) // scala.collection.immutable.Vector
// 多个元素追加
val v3 = v1 ++:Vector(3,4)
println(v3) //Vector(1, 2, 3, 4)
// 多个元素追加
val v4 = v1.++(Vector(3,4))
println(v4) //Vector(1, 2, 3, 4)
// 单个插入,在头部插入元素并生成一个新的Vector
val v5 = -1 +: 0 +: v1
println(v5) //Vector(-1, 0, 1, 2)
// 多个元素插入
val v6 = Vector(-1,0) ++: v1
println(v6) //Vector(-1, 0, 1, 2)
// 多个元素插入
val v7 = Vector(-1,0).++(v1)
println(v7) //Vector(-1, 0, 1, 2)
3.4 Vector 修改元素
val v1 = Vector(1, 2, 3)
println(v1)
//由于Vectors结构是不可变的,所以您不能通过修改vector中元素的方法来返回一个新的vector
v1(0)=100 //value update is not a member of scala.collection.immutable.Vector[Int]
//可以通过update方法从一个单独的元素中创建出区别于给定数据结构的新vector结构
val v2 = v1.updated(0,100)
println(v2)
从上面例子的最后一行我们可以看出,update方法的调用并不会改变vec的原始值。与元素访问类似,vector的update方法的运行时间也是“相对高效的固定时间”。对vector中的某一元素进行update操作可以通过从树的根节点开始拷贝该节点以及每一个指向该节点的节点中的元素来实现。这就意味着一次update操作能够创建1到5个包含至多32个元素或者子树的树节点。当然,这样做会比就地更新一个可变数组败家很多,但比起拷贝整个vector结构还是绿色环保了不少。
由于vector在快速随机选择和快速随机更新的性能方面做到很好的平衡,所以它目前正被用作不可变索引序列的默认实现方式。
3.6 Vector 元素排序
val v1 = Vector(3, 1, 5, 4, 7, 6, 9)
// 排序(比较两个值得哈希值) 默认升序排列
val v2 = v1.sorted
println(v2.toBuffer) //ArrBuffer(1, 3, 4, 5, 6, 7, 9)
// 排序 降序排列
val v3 = v1.sorted.reverse
println(v3.toBuffer) //ArrayBuffer(9, 7, 6, 5, 4, 3, 1)
// 排序 默认升序排列
val v4 = v1.sortBy(a => a)
println(v4.toBuffer) //ArrayBuffer(1, 3, 4, 5, 6, 7, 9)
// 排序 降序排列
val v5 = v1.sortBy(a => a).reverse
println(v5.toBuffer) //ArrayBuffer(9, 7, 6, 5, 4, 3, 1)
// 排序 升序排列
val v6 = v1.sortWith(_ < _)
println(v6.toBuffer) //ArrayBuffer(1, 3, 4, 5, 6, 7, 9)
// 排序 降序排列
val v7 = v1.sortWith(_ > _)
println(v7.toBuffer) ////ArrayBuffer(9, 7, 6, 5, 4, 3, 1)
3.7 Vector 其他操作
val v1 = Vector[Int](1, 2, 3)
// 检查是否存在某个值
println(v1.contains(1)) // true
println(v1.contains(11)) // false
// 转换成字符串
val str: String = v1.mkString(",")
println(str) //1,2,3
// 转换成字符串,指定头尾与分隔符
val str2 = v1.mkString("[", ",", "]")
println(str2) //[1,2,3]
// 删除前 2 位元素
val v2 = v1.drop(2)
println(v2.toBuffer) //ArrayBuffer(3)
// 反转
val v3 = v1.reverse
println(v3.toBuffer) //ArrayBuffer(3, 2, 1)
//Array 的转换操作
val v4 = Vector(1,3,2,5,4)
v4
.map((x:Int)=>x*2) //每个元素 乘2
.sortBy((x:Int)=>x) //按照元素顺序排序
.reverse //将数组反转
.foreach(println(_))
/**
* 10
* 8
* 6
* 4
* 2
*/
//上面代码可以简写成
v4.map(_*2).sortBy(x=>x).reverse.foreach(println)
// 字符串数组 转换操作
val strVector = Vector("hello you","hello world")
val strVector2 = strVector
.map(x=>{
val fields = x.split(" ") // 按照空格分隔
fields
}).flatten
println(strVector2.toBuffer) //ArrayBuffer(hello, you, hello, world)
//上面代码简写
val strVector3 = strVector.flatMap(x=>x.split(" "))
println(strVector3.toBuffer) //ArrayBuffer(hello, you, hello, world)
// 去重
val strVector4 = strVector.flatMap(_.split(" ")).distinct
println(strVector4) // Vector(hello, you, world)
4. Stack
如果您想要实现一个后入先出的序列,那您可以使用Stack。您可以使用push向栈中压入一个元素,用pop从栈中弹出一个元素,用top查看栈顶元素而不用删除它。所有的这些操作都仅仅耗费固定的运行时间。
ArrayStack 是另一种可变栈的实现,用一个可根据需要改变大小的数组做为支持。它提供了快速索引,使其通常在大多数的操作中会比普通的可变堆栈更高效一点。
4.1 Stack 初始化
// 定义一个不可变的 Stack
val s1 = scala.collection.immutable.Stack.empty
println(s1) //Stack()
// 定义一个不可变的 Stack
val s2 = immutable.Stack(1,2,3)
println(s2) //Stack(1, 2, 3)
// 定义一个可变的 Stack
val s3 = mutable.Stack(1 to 5:_*)
println(s3) //Stack(1, 2, 3, 4, 5)
4.2 Stack 查看元素
// 定义一个可变的 Stack
val s1 = mutable.Stack(1 to 5:_*)
println(s1) //Stack(1, 2, 3, 4, 5)
// 查找大于3 的元素
val s2 = s1.filter(_>3)
println(s2) //Stack(4, 5)
println(s1.top) // 查找栈顶元素 1
println(s1(0)) // 查找下标为 0 的元素 1
println(s1.max) // 查找最大值 5
println(s1.min) // 查找最小值 1
println(s1.length) // 查看长度 5
4.3 Stack 增加元素
// 定义一个可变的 Stack
val s1 = new scala.collection.mutable.Stack[Int]
println(s1) //Stack()
s1.push(1)
println(s1) //Stack(1)
// 后入先出
s1.push(2)
println(s1) //Stack(2, 1)
s1.push(3,4,5)
println(s1) //Stack(5, 4, 3, 2, 1)
val s5 = mutable.Stack(1,2)
val s6 = mutable.Stack(3,4)
// 合并两个Stack
val s7 = s5.++:(s6)
println(s7) //Stack(3, 4, 1, 2)
4.4 Stack 修改元素
val s1 = mutable.Stack(1 to 5:_*)
// 更新元素
s1(0)=10
println(s1) //Stack(10, 2, 3, 4, 5)
s1.update(1,20)
println(s1) //Stack(10, 20, 3, 4, 5)
val s2 = s1.updated(2,30)
println(s2) //Stack(10, 20, 30, 4, 5)
4.5 Stack 删除元素
val s1 = mutable.Stack(1 to 5:_*)
println(s1) //Stack(1, 2, 3, 4, 5)
//移除栈顶元素
s1.pop()
println(s1) //Stack(2, 3, 4, 5)
// 删除前两个元素
val s2 = s1.drop(2)
println(s2) //Stack(4, 5)
// 清空
s1.clear()
println(s1) // Stack()
5. Queue
Queue是一种与stack很相似的数据结构,除了与stack的后入先出不同,Queue结构的是先入先出的。
Scala除了提供了可变与不可变的Queue。你需要使用+= 和++=操作符进行添加的方式来替代排队方法。 在一个可变队列中,出队方法将只移除头元素并返回该队列。
5.1 Queue 初始化
val q1 = new scala.collection.mutable.Queue[String]
println(q1) // Queue()
val q2 = Queue(1,2,3)
println(q2) //Queue(1, 2, 3)
val q3 = scala.collection.immutable.Queue(4,5,6)
println(q3) //Queue(4, 5, 6)
val q4 = Queue(1 to 5:_*)
println(q4) //Queue(1, 2, 3, 4, 5)
5.2 Queue 查看元素
val q1 = Queue(1 to 5:_*)
println(q1) //Queue(1, 2, 3, 4, 5)
println(q1.head)
// 查找大于3 的元素
val s2 = q1.filter(_>3)
println(s2) //Stack(4, 5)
println(q1.dequeue()) // 移除头部元素并返回队列
println(q1)
println(q1(0)) // 查找下标为 0 的元素 2
println(q1.max) // 查找最大值 5
println(q1.min) // 查找最小值 1
println(q1.length) // 查看长度 5
5.3 Queue 增加元素
val q1 = Queue(1 to 3:_*)
//头部插入
val q2 = q1.++:(Queue(4))
println(q2) //Queue(4, 1, 2, 3)
// 尾部追加
val q3 = q1.++(Queue(2,3))
println(q3) //Queue(1, 2, 3, 2, 3)
5.4 Queue 修改元素
val q1 = scala.collection.immutable.Queue(1 to 3: _*)
val q2 = q1.updated(0,10)
println(q2) //Queue(10, 2, 3)
5.5 Queue 删除元素
val q1 = Queue(1 to 5: _*)
// 移除前两个元素
val q2 = q1.drop(2)
println(q2) //Queue(3)
// 取差集
val q3 = q2.diff(Queue(3,4,6))
println(q3) //Queue(4, 5)
6. Stream
流Stream与List很相似,只不过其中的每一个元素都经过了一些简单的计算处理。也正是因为如此,stream结构可以无限长。只有那些被要求的元素才会经过计算处理,除此以外stream结构的性能特性与List基本相同。
List通常使用 :: 运算符来进行构造,stream使用外观上很相像的#::。
val s1 = Stream.range(1,1000000000)
println(s1) //Stream(1, ?)
val s2 = 1 #:: 2 #:: 3 #:: Stream.empty
println(s2) //Stream(1, ?)
// 该stream的头结点是1,尾是2和3.
// 尾部并没有被打印出来,因为还没有被计算。
// stream被特别定义为懒惰计算,并且stream的toString方法很谨慎的设计为不去做任何额外的计算。
//.take(3).force // Stream(1, 2, 3)
val fibs = fibFrom(1, 1).take(7)
println(fibs.toList) //List(1, 1, 2, 3, 5, 8, 13)
/**
* 这里讲一个以两个给定的数字为起始的斐波那契数列转换成stream。
* 斐波那契数列的定义是,序列中的每个元素等于序列中在它之前的两个元素之和。
* 这个函数看起来比较简单。
* 序列中的第一个元素显然是a,其余部分是以b和位于其后的a+b为开始斐波那契数列。
* 这段程序最大的亮点是在对序列进行计算的时候避免了无限递归。
* 如果函数中使用::来替换#::,那么之后的每次调用都会产生另一次新的调用,从而导致无限递归。
* 在此例中,由于使用了#::,等式右值中的调用在需要求值之前都不会被展开。
* 这里尝试着打印出以1,1开头的斐波那契数列的前几个元素
*/
def fibFrom(a: Int, b: Int): Stream[Int] = {
a #:: fibFrom(b, a + b)
}
7. Iterator(迭代器)
迭代器不是一个容器,更确切的说是逐一访问容器内元素的方法。迭代器Iterator的两个基本操作是next和hasNext。调用it.next()会返回迭代器的下一个元素,并且更新迭代器的状态。在同一个迭代器上再次调用next,会产生一个新元素来覆盖之前返回的元素。如果没有元素可返回,调用next方法会抛出一个NoSuchElementException异常。你可以调用迭代器的hasNext方法来查询容器中是否有下一个元素可供返回。
7.1 Iterator 初始化
val it1 = Iterator("a", "number", "of", "words")
println(it1) //non-empty iterator
//由于Iterator用一次后就消失了,如果要用两次,需要toList或者使用duplicate:
val (a,b) = Iterator(1,3,5,7) duplicate // a = b = non-empty iterator
7.2 Iterator 遍历元素
- while 遍历
val it1 = Iterator("a", "number", "of", "words")
while (it1.hasNext){
print(it1.next()+"\t") //a number of words
}
// 遍历过后检查是否还有元素
println(it1.hasNext) // false
// 遍历过后再访问里面的元素会抛出异常
println(it1.next()) //next on empty iterator
- for 遍历
for(e<- Iterator(1,3,5,7)) {
println(e)
}
- foreach 遍历
Iterator(1,3,5,7) foreach println
- map 遍历
val list1 = (Iterator(1,3,5,7) map (1*) toList)
println(list1) //List(1, 3, 5, 7)
- dropWhile 遍历并过滤
val list2 = (Iterator(1,3,5,7) dropWhile (5>) toList)
println(list2) //List(5, 7)