19.3. 数据结构分析

Go 入门指南 /

[ 这个章节的代码，可以在 goto_v1\store.go 中找到 ]

当我们的应用在生产环境中运行的时候，它将接收到很多短网址的请求，并且还会收到很多将一个长网址变短的请求。我们的程序会用哪些数据结构存储这些数据？如在章节 19.2 中的 url 类型（A）和（B）都是一个字符串，并且它们彼此相关：我们可以将（B）作为键，通过它去获取（A）的值，它们相互映射。为了将数据存储在内存中，我们需要这样一种结构，几乎所有编程语言都存在的，用不同的名字作下标的 hash 表、字典等。

Go 有一个这样的内置的 map ：一个 map[string]string

键的类型写在 [ ] 里面，后面跟的是值的类型；可以去章节 8 学习所有和 map 有关的知识。在任何一个不平凡的程序中，给特定的类型使用一个名称是很有用的。在 Go 中，我们使用关键字 type 可以做到，所以我们定义一个： type URLStore map[string]string

它将短网址映射到长网址，并且都是字符串。

要创建一个该类型命名的变量 m，只需使用：

m := make(URLStore)

假设我们想要存储 goto/a 到 google.com/ 的映射到 m , 我们可以使用这样的语句： m["a"] = "http://google.com/"

（在键始终保持不变的前提下，我们只需要存储 goto/ 的后缀来作为一个键）。要检索指定的 a 对应的长网址，我们写： url := m["a"]

然后 url 的值等于「http://google.com/」。

注意：使用 := 我们不需要说明 url 是 string 类型：编译器会从右侧的值中推导出类型。

使它线程安全：我们的 URLStore 变量是一个重要的内存数据存储，在这里：一旦我们获得一些流量，将会有许多重定向类型的请求。这些实际上只是读的操作：使用短网址作为键读取，并且将长网址作为值返回。但是 Add 类型的请求是不同的，他们改变了我们的 URLStore，添加了新的键值对。当我们的服务一次性获得需要更新类型的请求时，可能会出现以下问题：添加操作可能被另一个相同类型的请求打断，并且长网址的值可能不会被写入。也可能会将读取的内容一起修改，导致读取到一个错误的结果。我们的 map 不能保证在开始一个更新操作的时候，一个新的更新开始之前，它会完全终止。换句话说：一个 map 不是线程安全的，它将会并发处理许多的请求，所以我们必须使我们的 URLStore 类型安全的从一个单独的线程去访问。最简单和经典的方法就是为它添加一个锁。在 Go 中，这是一个标准库中 sync 包中的 Mutex 类型，我们必须将它导入到我们的代码中（详细的锁定参见：章节 9.3 ）。

我们将我们的 URLStore 的类型更改成一个 struct 类型（就这像在 C 或者 Java 中一个字段的集合，我们在第 10 章解释了 struct ）, 它有两个字段： map 和一个 sync 包中的 RWMutex ：

import “sync”

type URLStore struct {

    urls map[string]string    // map 是从短网址到长网址

    mu    sync.RWMutex

}

一个 RWMutex 有两个锁：一个用于读取，一个用于写入。多个客户端可以同时获得读取锁，但是只能有一个客户端能够获得写入锁（禁用所有读取器），从而有效的序列化更新，使他们连续的工作。

我们将在一个 Get 方法中实现重定向我们读类型的请求，并且我们添加一个 Set 方法来处理写的请求。Get 方法看起来就像这样：

func (s *URLStore) Get(key string) string {

    s.mu.RLock()

    url := s.urls[key]

    s.mu.RUnlock()

    return url

}

它传入一个 key （短网址），并将相应的 map 中的值作为 url 返回。这个方法用在一个变量 s 上，它是一个指向我们的 URLStore 的指针（参见：章节 4.9 ）。但是在读取值之前，我们使用 s.mu.RLock() 设置了一个读锁，所以没有更新能够打断读取。读取之后我们解锁，所以等待的更新可以开始执行。如果在 map 中不存在 key 怎么办？一个字符串类型的零值（空字符串）将被返回。注意面向对象语言中熟悉的 . 符号：方法 RLock() 在 s 的 mu 字段上被调用。

Set 方法需要同时传入一个 key 和一个 url ，并且必须使用一个写锁 Lock() 来阻止在同一时间的任何其他的更新。它返回一个布尔类型的 true 或者 false 值来表示 Set 是否成功。

func (s *URLStore) Set(key, url string) bool {

    s.mu.Lock()

    _, present := s.urls[key]

    if present {

        s.mu.Unlock()

        return false

    }

    s.urls[key] = url

    s.mu.Unlock()

    return true

}

通过 _, present := s.urls[key] 这种形式，我们可以测试看看我们的 map 是否已经包含了这个 key，存在 present 变成 true，否则为 false。这个就是我们在 Go 代码中经常遇到的所谓的 逗号 ok 模式。如果 key 已经存在， Set 返回一个布尔型的值 false ，并且因为我们从方法返回， map 不会更新（所以我们不允许短网址被重用）。如果这个 key 不存在，我们添加它到 map，并且返回 true。左侧的 _ 是一个值的占位符，并且我们表明了不会使用它，因为我们将它分配给了 _ 。请注意，要尽可能快的（更新之后）解锁我们的 URLStore 。

使用 defer 来简化代码：

在这种情况下，因为代码简单，它可以很容易的记住去执行 Unlock 。然而，在非常复杂的代码中，就可能会被忘记了或者放在错误的地方，导致的问题难以追踪。对于这种情况，Go 有一个特殊的关键字 defer （参见：章节 6.4 ），在这种情况下，它允许在执行完锁定后立即发出解锁信号，但其效果是 Unlock() 只会在函数返回之前才会被执行。

Get 可以被简化为（我们已经去除了局部变量 url）：

func (s *URLStore) Get(key string) string {

    s.mu.RLock()

    defer s.mu.RUnlock()

    return s.urls[key]

}

Set 的逻辑也变得非常的清晰（我们不需要再考虑解锁）：

func (s *URLStore) Set(key, url string) bool {

    s.mu.Lock()

    defer s.mu.Unlock()

    _, present := s.urls[key]

    if present {

        return false

    }

    s.urls[key] = url

    return true

}

URLStore 工厂函数：

URLStore 结构体包含一个 map 字段，在使用它之前，必须要使用 make 初始化。在 Go 中通过定义个 New 前缀的函数来完成创建一个结构体的实例，该函数返回一个被初始化的类型的实例（在这里，大多数情况下，它是一个指向它的指针）：

func NewURLStore() *URLStore {

    return &URLStore{ urls: make(map[string]string) }

}

在返回中，我们制造了一个 URLStore 字面，并且初始化 map ，锁不需要特意初始化；这是在 Go 中制造结构体对象的标准方法。 & 是一个地址运算符，将我们返回的内容转换为指针，因为 NewURLStore 需要返回一个指针 *URLStore 。我们只是调用这个函数来制造一个 URLStore 变量 s ： var s = NewURLStore()

使用我们的 URLStore：

向我们的 map 添加一对新的短/长 URL ，我们需要做的是调用 s 上的 Set 方法，并且由于这是一个布尔值，我们能立即包装它到一个 if 语句中：

if s.Set("a", "http://google.com") {

    // success

}

要取回指定短网址 a 的长网址，我们将调用 s 上的 Get 方法，并将结果放到一个 url 变量中：

if url := s.Get(“a”); url != “” {

    // redirect to url

} else {

    // key not found

}

在 Go 中，我们可以使用它的一个特性， if 可以在条件之前，使用一个初始化语句。我们还需要一个 Count() 方法，来为我们计算 map 中的键值对的数量，这是由一个内置的 len 函数实现的。

func (s *URLStore) Count() int {

    s.mu.RLock()

    defer s.mu.RUnlock()

    return len(s.urls)

}

我们如何计算指定的长网址的短网址？我们使用一个函数 genKey(n int) string {…} 并且它的整形参数我们赋予它 s.Count() 当前的值。

[ 确切的算法并不重要，可以在 key.go 中找到示例代码 ]

我们现在可以做一个 Put 方法，它需要一个长网址，使用 genKey 生成他的短网址 key ，使用 Set 方法，将长网址使用这个（短网址） key 作为下标储存，并返回它的 key：

func (s *URLStore) Put(url string) string {

    for {

        key := genKey(s.Count())

        if s.Set(key, url) {

            return key

        }

    }

    // 不应该到这里

    return ""

}

for 循环一直重试 Set ，直到它成功（表示我们生成了一个尚未存在的短网址）。到现在为止，我们已经定义了我们的数据存储和处理它的函数（可以在 store.go 中找到代码）。但是这本身并没有做任何事，我们还必须去定义一个 web 服务器去提供添加与重定向服务。

本文章首发在 LearnKu.com 网站上。

本译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。

原文地址：https://learnku.com/docs/the-way-to-go/1...

译文地址：https://learnku.com/docs/the-way-to-go/1...

Markdown 文本

贡献者：1

19.3. 数据结构分析

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

19.3. 数据结构分析

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录