大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
Go语言中的Map和List实现有序Map
Map定义：
Go 中 Map是一种无序的键值对的集合。Map最重要的一点是通过key来快速检索数据，key类似于索引，指向数据的值。Map是一种集合，所以我们可以像迭代数组和切片那样迭代它。不过，Map是无序的，我们无法决定它的返回顺序，这是因为Map是使用链式hash表来实现的。
其他语言中的实现：
在C++ STL 中map 采用红黑树实现，可以实现有序的Map.
在PHP中，Array就是一个有序的map
Go 中实现：
type MapList struct {
dataMap map[string]*list.Element
dataList *list.List
}
这个实现方法的主要的方法是用空间换取时间。通过list 和 map 两种数据结构，保存相同的一份数据。list 用来做顺序遍历，map 用来做查找，删除操作。
为了把对象保存到 map中，我们还需要定义一个接口
type Keyer interface {
GetKey() string
}
主要实现代码如下：
package main
import (
"container/list"
"fmt"
)
type Keyer interface {
GetKey() string
}
type MapList struct {
dataMap map[string]*list.Element
dataList *list.List
}
func NewMapList() *MapList {
return &MapList{
dataMap: make(map[string]*list.Element),
dataList: list.New(),
}
}
func (mapList *MapList) Exists(data Keyer) bool {
_, exists := mapList.dataMap[string(data.GetKey())]
return exists
}
func (mapList *MapList) Push(data Keyer) bool {
if mapList.Exists(data) {
return false
}
elem := mapList.dataList.PushBack(data)
mapList.dataMap[data.GetKey()] = elem
return true
}
func (mapList *MapList) Remove(data Keyer) {
if !mapList.Exists(data) {
return
}
mapList.dataList.Remove(mapList.dataMap[data.GetKey()])
delete(mapList.dataMap, data.GetKey())
}
func (mapList *MapList) Size() int {
return mapList.dataList.Len()
}
func (mapList *MapList) Walk(cb func(data Keyer)) {
for elem := mapList.dataList.Front(); elem != nil; elem = elem.Next() {
cb(elem.Value.(Keyer))
}
}
type Elements struct {
value string
}
func (e Elements) GetKey() string {
return e.value
}
func main() {
fmt.Println("Starting test...")
ml := NewMapList()
var a, b, c Keyer
a = &Elements{"Alice"}
b = &Elements{"Bob"}
c = &Elements{"Conrad"}
ml.Push(a)
ml.Push(b)
ml.Push(c)
cb := func(data Keyer) {
fmt.Println(ml.dataMap[data.GetKey()].Value.(*Elements).value)
}
fmt.Println("Print elements in the order of pushing:")
ml.Walk(cb)
fmt.Printf("Size of MapList: %d \n", ml.Size())
ml.Remove(b)
fmt.Println("After removing b:")
ml.Walk(cb)
fmt.Printf("Size of MapList: %d \n", ml.Size())
}
输出结果：
Starting test...
Print elements in the order of pushing:
Alice
Bob
Conrad
Size of MapList: 3
After removing b:
Alice
Conrad
Size of MapList: 2
优点：
红黑树的插入、删除、查找的复杂度都是 O(logn), 而这个实现插入查找删除的复杂度都是 O(1), 可以说是一种非常好的数据结构。
缺点：
使用了两个数据结构，空间占用稍微大了一点。但是和树的实现比，这个占用也不算非常大。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/193192.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
