本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Splay Tree

伸展树/分裂树（Splay Tree）

伸展树是一种数据结构，在结构上与平衡二叉搜索树相同。 在伸展树上执行的每个操作都会导致重新调整，以便快速访问最近运行的值。 在每次访问时，树被重新排列，并且使用一组特定的旋转将访问的节点移动到树的根，这些旋转一起被称为Splaying。

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Ring Buffer

环形缓冲区（Ring Buffer）

也称为循环缓冲区。

基于数组的队列的问题是在队列后面添加新项目很快，O(1)，但是从队列前面删除项目很慢，O(n)。删除速度很慢，因为它需要在内存中移动剩余的数组元素。

实现队列的更有效方法是使用环形缓冲区或循环缓冲区。 这是一个概念性地回绕到开头的数组，因此您永远不必删除任何项目。 所有操作都是O(1)。

原则上它是如何工作的。 我们有一个固定大小的数组，比如5项：

[    ,    ,    ,    ,     ]
 r
 w

最初，数组为空，读（r）和写（w）指针位于开头。

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Bounded Priority Queue

有界优先队列（Bounded Priority queue）

有界优先级队列类似于常规优先队列，除了可以存储的元素数量有固定的上限。在队列处于满容量时，将新元素添加到队列时，具有最高优先级值的元素将从队列中弹出。

例子

假设我们有一个最大大小为5的有界优先级队列，它具有以下值和优先级：

1
2

Value:    [ A,   B,   C,    D,    E   ]
Priority: [ 4.6, 3.2, 1.33, 0.25, 0.1 ]

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Hash Set

哈希集合（Hash Set）

集合是元素的集合，有点像数组但有两个重要的区别：集合中元素的顺序不重要，每个元素只能出现一次。

如果以下是数组，它们都会有所不同。 但是，它们都代表相同的集合：

1
2
3
4

[1 ,2, 3]
[2, 1, 3]
[3, 2, 1]
[1, 2, 2, 3, 1]

因为每个元素只能出现一次，所以将元素写入的次数并不重要 —— 只有其中一个元素有效。

注意：当我有一组对象但不关心它们的顺序时，我经常更喜欢使用数组上的集合。使用集合与程序员通信，元素的顺序并不重要。 如果你正在使用数组，那么你不能假设同样的事情。

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Ordered Set

有序集（Ordered Set）

我们来看看苹果如何实现有序集。

Here is the example about how it works
以下是有关其工作原理的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

let s = AppleOrderedSet<Int>()

s.add(1)
s.add(2)
s.add(-1)
s.add(0)
s.insert(4, at: 3)

print(s.all()) // [1, 2, -1, 4, 0]

s.set(-1, at: 0) // 已经有-1在index: 2，因此这个操作不做任何事情

print(s.all()) // [1, 2, -1, 4, 0]

s.remove(-1)

print(s.all()) // [1, 2, 4, 0]

print(s.object(at: 1)) // 2

print(s.object(at: 2)) // 4

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Multiset

多重集合（Multiset）

多重集合（也称为bag，简称多重集）是一种类似于常规集的数据结构，但它可以存储同一元素的多个实例。

例如，如果我将元素1,2,2添加到常规集中，则该集将仅包含两个项，因为第二次添加2无效。

1
2
3
4

var set = Set<Int>()
set.add(1) // set is now [1]
set.add(2) // set is now [1, 2]
set.add(2) // set is still [1, 2]

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Bloom Filter

布隆过滤器(Bloom Filter)

介绍

布隆过滤器是一种节省空间的数据结构，可以告诉您元素是否存在于集合中。

这是一个概率数据结构：对布隆过滤器的查询返回false，意味着该元素肯定不在集合中，或者是true，这意味着元素可能在集合中。

误报的可能性很小，即使查询返回true，元素实际上也可能不在集合中。 但是永远不会有任何漏报：如果查询返回false，你可以保证，那么元素确实不在集合中。

所以布隆过滤器告诉你，“绝对不是”或“可能是的”。

作者和本书概要

弗兰西斯·培根(Francis Bacon，1561–1626)是英国文艺复兴时期最伟大的哲学家和文学家，“英国唯物主义和整个现代实验科学的真正鼻祖”。

豆瓣：《培根随笔》

内容

论真理

真正可怕的，并不是那种人人都难以避免的一念之差，而是那种深入习俗、盘踞于人心深处的谬误与偏见。

论死亡

“死亡是大自然赐给人类的一种恩惠。”

一个坚定执著、有信念的心灵不会因对死亡的畏惧而陷入恐怖。

作者和本书概要

爱默生（Ralph Waldo Emerson）， 美国思想家、文学家，诗人。爱默生是确立美国文化精神的代表人物。

豆瓣：《爱默生随笔》

内容

论爱情

成熟的年龄和迂腐的学识会使人类的花样年华逐渐凋零。

在思想或是真理的天空下，看任何事物都是美好的。在记忆的天空下，看每一段人生经历中的任何事物，则总是苦涩的。仔细地体味总是充满伤感，而热情的计划总是让人充满希望，感觉崇高。

真挚情感的最初流露与和谐仁爱是人的天性中最为迷人的风景。

爱的世界永远是人创造的，如果不尝试着去收回那些违背人性、诋毁社会本能的言语，理性而无情的哲学家们决不可能描述出每一个彷徨于此的年轻心灵所蒙受到的爱情恩惠。

本文是对 Swift Algorithm Club 翻译的一篇文章。

Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。

🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。

本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Boyer-Moore String Search

Boyer-Moore字符串搜索(Boyer-Moore String Search)

这个主题已经有教程 here

目标：在纯Swift中编写字符串搜索算法，而无需导入Foundation或使用NSString的rangeOfString()方法。

换句话说，我们想在String上实现一个indexOf(pattern：String)扩展，它返回在字符串里面第一次出现搜索模式的String.Index，如果找不到模式则返回nil 。