数据结构

Last updated 2 years ago

Was this helpful?

数据结构

版本 1 - 数据结构和前端界面

第 1 个版本的代码 goto_v1 见。

19.3 数据结构

（本节代码见。）

当程序运行在生产环境时，会收到很多短网址的请求，同时会有一些将长 URL 转换成短 URL 的请求。我们的程序要以什么样的结构存储这些数据呢？中 (A) 和 (B) 两种 URL 都是字符串，此外，它们相互关联：给定键 (B) 能获取到值 (A)，他们互相映射 (map)。要将数据存储在内存中，我们需要这种结构，它们几乎存在于所有的编程语言中，只是名称有所不同，例如“哈希表”或“字典”等。

Go 语言就有这种内建的映射 (map)：map[string]string。

键的类型写在 [ 和 ] 之间，紧接着是值的类型。有关映射的所有知识详见。为特定类型指定一个别名在严谨的程序中非常实用。Go 语言中通过关键字 type 来定义，因此有定义：

type URLStore map[string]string

它从短 URL 映射到长 URL，两者都是字符串。

要创建那种类型的变量，并命名为 m，使用：

m := make(URLStore)

假设 http://goto/a 映射到 http://google.com/ ，我们要把它们存储到 m 中，可以用如下语句：

m["a"] = "http://google.com/"

（键只是 http://goto/ 的后缀，其前缀总是不变的。）

要获得给定 "a" 对应的长 URL，可以这么写：

url := m["a"]

此时 url 的值等于 http://google.com/。

注意，使用了 := 就不需要指明 url 的类型为 string，编译器会从右侧的值中推断出来。

使程序线程安全

import "sync"
type URLStore struct {
	urls map[string]string		// map from short to long URLs
	mu sync.RWMutex
}

RWMutex 有两种锁：分别对应读和写。多个客户端可以同时设置读锁，但只有一个客户端可以设置写锁（以排除所有的读锁），有效地串行化变更，使他们按顺序生效。

我们将在 Get() 函数中实现 Redirect 服务的读请求，在 Set 函数中实现 Add 服务的写请求。Get() 函数类似下面这样：

func (s *URLStore) Get(key string) string {
	s.mu.RLock()
	url := s.urls[key]
	s.mu.RUnlock()
	return url
}

Set() 函数同时需要 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 中是否已经包含该键，包含则 present 为 true，否则为 false。这种形式称为“逗号 ok 模式”，在 Go 代码中会频繁出现。如果键已存在，Set() 函数直接返回布尔值 false，map 不会被更新（这样可以保证短 URL 不会重复）。如果键不存在，把它加入 map 中并返回 true。左侧 _ 是一个值的占位符，赋值给 _ 来表明我们不会使用它。注意在更新后尽早调用 Unlock() 来释放对 URLStore 的锁定。

使用 defer 简化代码

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) }
}

在 return 语句中，创建了 URLStore 字面量实例，其中包含初始化了的 map 映射。锁无需特别指明初始化，这是 Go 创建结构体实例的惯例。& 是取址运算符，它将我们要返回的内容变成指针，因为 NewURLStore() 返回类型是 *URLStore。然后调用该函数来创建 URLStore 变量：

var store = NewURLStore()

使用 URLStore

要新增一对短/长 URL 到 map 中，我们只需调用 s 上的 Set() 方法，由于返回布尔值，可以把它包裹在 if 语句中：

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

要获取给定短 URL 对应的长 URL，调用 s 上的 Get() 方法，将返回值放入变量 url：

if url := s.Get("a"); url != "" {
	// 重定向到 url
} else {
	// 键未找到
}

这里我们利用 Go 语言 if 语句的特性，可以在起始部分、条件判断前放置初始化语句。另外还需要一个 Count() 方法以获取 map 中键值对的数量，可以使用内建的 len() 函数：

func (s *URLStore) Count() int {
	s.mu.RLock()
	defer s.mu.RUnlock()
	return len(s.urls)
}

现在，我们可以创建一个 Put() 方法，接收一个长 URL，用 genKey() 生成其短 URL 键，调用 Set() 方法在此键下存储长 URL 数据，然后返回这个键：

func (s *URLStore) Put(url string) string {
	for {
		key := genKey(s.Count())
		if s.Set(key, url) {
			return key
		}
	}
	// shouldn’t get here
	return ""
}

链接

Previous短网址项目简介 Next用户界面：web 服务端

Last updated 2 years ago

Was this helpful?