精华内容
下载资源
问答
  • go 有序map,用于json输出有序key的对象和后端有序循环map取值
  • Go语言中的Map和List实现有序Map

    千次阅读 2018-09-18 18:02:55
    Go语言中的Map和List实现有序Map Map定义: Go 中 Map是一种无序的键值对的集合。Map最重要的一点是通过key来快速检索数据,key类似于索引,指向数据的值。Map是一种集合,所以我们可以像迭代数组和切片那样迭代...

    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), 可以说是一种非常好的数据结构。

    缺点:

    使用了两个数据结构,空间占用稍微大了一点。但是和树的实现比,这个占用也不算非常大。

    展开全文
  • java有序map

    2017-04-28 11:43:00
    为了让Map按照插入顺序显示,可以使用LinkedHashMap吧。 它内部有一个链表,保持插入的顺序。迭代的时候,也是按照插入顺序迭代,而且迭代比HashMap快。 转载于:...

    我们知道TreeMap的key是有顺序的,是自然顺序,也可以指定比较函数。

    TreeMap默认不是按插入的顺序。 


    为了让Map按照插入顺序显示,可以使用LinkedHashMap吧。

    它内部有一个链表,保持插入的顺序。迭代的时候,也是按照插入顺序迭代,而且迭代比HashMap快。

    转载于:https://www.cnblogs.com/lixiaoran/p/6780898.html

    展开全文
  • golang 实现 key有序map

    千次阅读 2019-03-26 16:11:03
    key有序(例如交易所订单撮合),C++ 的stl map 实现了key有序,实际上是TreeMap是基于树(红黑树)的实现方式,即添加到一个有序列表,在O(log n)的复杂度内通过key值找到value,优点是空间要...

    原文链接

    摘要: Golang map实现原理是hash
    map(核心元素是桶,key通过哈希算法被归入不同的bucket中),key是无序的,很多应用场景可能需要map
    key有序(例如交易所订单撮合),C++ 的stl map
    实现了key有序,实际上是TreeMap是基于树(红黑树)的实现方式,即添加到一个有序列表,在O(log
    n)的复杂度内通过key值找到value,优点是空间要求低,但在时间上不如HashMap。

    Golang map实现原理是hash map(核心元素是桶,key通过哈希算法被归入不同的bucket中),key是无序的,很多应用场景可能需要map key有序(例如交易所订单撮合),C++ 的stl map 实现了key有序,实际上是TreeMap是基于树(红黑树)的实现方式,即添加到一个有序列表,在O(log n)的复杂度内通过key值找到value,优点是空间要求低,但在时间上不如HashMap。

    闲来用go map + slice切片,实现了一套key有序map数据结构,就是空间换时间的玩法, 实质是map 负责存k v, slice负责维护k的有序索引位置(查找key采用的是2分法),实现后赠改删时间负责度是 O(log2n), 。
    优化的一点思考:实际上主要就是在slice上维护k位置时的增改删费操作,这时候我们可根据具体应用在2分查找上下点文章。 例如可能所存的数据结构频繁操作的节点只有前面一部分,这时候我们可以加个逻辑,操作时slice时先2查找 slice子集(例如头部热点),这样可能很多增改删操作在第一时间就解决了,整体性能会有很大提升, 最好根据应用场景来具体分析解决。下面给出代码。

    Order_Map:

    package Order_Map
    
    func findIndexByBinarySearch(s []int, k int) (int, bool) {
    
        lo, hi := 0, len(s)
    
        var m int
    
        max := len(s)
    
        if max == 0 {
    
            return 0, false
    
        }
    
        res := false
    
        for lo <= hi {
    
            m = (lo + hi) >> 1
    
            if m == 0 && s[0] > k {
    
                return 0, res
    
            }
    
            if m == max-1 && s[max-1] < k {
    
                return m + 1, res
    
            }
    
            if s[m] < k && s[m+1] > k {
    
                return m + 1, res
    
            }
    
            if s[m] > k && s[m-1] < k {
    
                return m, res
    
            }
    
            if s[m] < k {
    
                lo = m + 1
    
            } else if s[m] > k {
    
                hi = m - 1
    
            } else {
    
                return m, true
    
            }
    
        }
    
        return -1, false
    
    }
    
    type Int_Map struct {
    
        dataMap  map[int]interface{}
    
        keyArray []int
    
    }
    
    func NewIntMap(cap int) *Int_Map {
    
        return &Int_Map{
    
            dataMap:  make(map[int]interface{}),
    
            keyArray: make([]int, 0, cap),
    
        }
    
    }
    
    func (m *Int_Map) Exists(key int) bool {
    
        _, exists := m.dataMap[key]
    
        return exists
    
    }
    
    func (m *Int_Map) Insert(key int, data interface{}) bool {
    
        m.dataMap[key] = data
    
        index, res := findIndexByBinarySearch(m.keyArray, key)
    
        if index == -1 {
    
            return false
    
        }
    
        if res == true { //存在则直接返回
    
            return true
    
        }
    
        if len(m.keyArray) == 0 {
    
            m.keyArray = append(m.keyArray, key)
    
            return true
    
        }
    
        //追加末尾
    
        if index >= len(m.keyArray) {
    
            m.keyArray = append(m.keyArray[0:], []int{key}...)
    
        } else if index == 0 { //追加头部
    
            m.keyArray = append([]int{key}, m.keyArray[:len(m.keyArray)]...)
    
        } else { //插入
    
            rear := append([]int{}, m.keyArray[index:]...)
    
            m.keyArray = append(m.keyArray[0:index], key)
    
            m.keyArray = append(m.keyArray, rear...)
    
        }
    
        return true
    
    }
    
    func (m *Int_Map) Erase(key int) {
    
        if !m.Exists(key) {
    
            return
    
        }
    
        index, res := findIndexByBinarySearch(m.keyArray, key)
    
        if res == false {
    
            return
    
        }
    
        delete(m.dataMap, key)
    
        if index == 0 {
    
            m.keyArray = m.keyArray[1:]
    
        } else if index == len(m.keyArray) {
    
            m.keyArray = m.keyArray[:len(m.keyArray)-2]
    
        } else {
    
            m.keyArray = append(m.keyArray[:index], m.keyArray[index+1:]...)
    
        }
    
    
    }
    
    func (m *Int_Map) Size() int {
    
        return len(m.keyArray)
    
    }
    
    func (m *Int_Map) GetByOrderIndex(index int) (int, interface{}, bool) {
    
        if index < 0 || index >= len(m.keyArray) {
    
            return -1, nil, false
    
        }
    
        key := m.keyArray[index]
    
        return key, m.dataMap[key], true
    
    }
    

    测试

    package main
    
    import (
    
        "Order_Map"
    
        "fmt"
    
    
        "math/rand"
    
    
        "reflect"
    
        "time"
    
    )
    
    func main() {
    
    
        t := time.Now()
    
        r := rand.New(rand.NewSource(time.Now().UnixNano()))
    
        testmap := Order_Map.NewIntMap(10000)
    
        t1 := t.Second()
    
        for i := 0; i < 10000; i++ {
    
            testmap.Insert(r.Intn(10000), r.Intn(10000))
    
        }
    
        t = time.Now()
    
        t2 := t.Second()
    
        fmt.Println("insert  time  span", t2-t1)
    
        testmap.Erase(88)
    
        for i := 0; i < testmap.Size(); i++ {
    
            k, v, _ := testmap.GetByOrderIndex(i)
    
            tmp_v := reflect.ValueOf(v)
    
            fmt.Println("k:", k, "---", "value:", tmp_v)
    
        }
    
    
        t = time.Now()
    
        t3 := t.Second()
    
        fmt.Println("range  time  span:", t3-t2)
    
    
    }
    
    展开全文
  • js实现简单的有序map

    2019-07-03 11:42:42
    原文:https://blog.csdn.net/themagickeyjianan/article/details/85608721 function SortMap(){ this._map = {}; } SortMap.prototype.add = function(key, value){ this._map[key] = value; } SortMap.pr...

    原文:https://blog.csdn.net/themagickeyjianan/article/details/85608721

    function SortMap(){
        this._map = {};
    }
     
    SortMap.prototype.add = function(key, value){
        this._map[key] = value;
    }
     
    SortMap.prototype.get = function(key){
        return this._map[key];
    }
     
    SortMap.prototype.printInfo = function(){
        for(var key in this._map){
            console.log(this._map[key]);
        }
    }
     
    var mapObj = new SortMap();
    mapObj.add("0", "JIANAN");
    mapObj.add("1", "bobo");
    mapObj.add("2", "xixi");
    mapObj.add("3", "xiaoming");
    mapObj.add("4", "lili");
     
    mapObj.printInfo();
     
    //console.log(mapObj.get("1"));
    //console.log(mapObj.get("3"));
     
    /**
    JIANAN
    bobo
    xixi
    xiaoming
    lili
    bobo
    undefined
     */
    
    展开全文
  • 简单对比map和unordered_map的性能。 map内部是红黑树,在插入元素时会自动排序,而无序容器unordered_map内部是散列表,通过哈希而不是排序来快速操作元素,使得效率更高。当你不需要排序时选择unordered_map的...
  • 实现有序map之go

    2017-11-06 23:15:41
    Go Map介绍 Go 中 Map是一种无序的键值对的集合。Map最重要的一点是通过key来快速检索数据,key类似于索引,指向数据的值。Map是一种集合,所以我们可以像迭代数组和切片那样迭代它。不过,Map是无序的,我们无法...
  • HashMap通过hashcode对其内容进行快速查找,而 TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。 HashMap 非线程安全 TreeMap...
  • Properties转换成有序Map

    千次阅读 2013-01-18 10:25:39
    Properties prop=new Properties();   FileInputStream inputStream=new FileInputStream(propertiesFileAddress);   ...TreeMap, String> treeMap=new TreeMap, String>((Map)prop);
  • 给HashMap排序,使之成为有序Map

    千次阅读 2017-07-27 16:45:26
    这个问题很多人都遇到过,很常见的一个方案是使用LinkedHashMap,因为LinkedHashMap可以记住元素放入的顺序,可以认为是真正的“有序”(想让HashMap有序是不可能的),我比较喜欢。然而问题是往往数据已经封装在了...
  • 获取LinkedHashMap中的头部元素(最早添加的元素... return map.entrySet().iterator().next(); } 获取LinkedHashMap中的末尾元素(最近添加的元素):时间复杂度O(n) public <K, V> Entry<K, V> ge.
  • 有序Map集合

    万次阅读 2019-06-22 08:32:07
    我们通常使用的Map集合是HashMap...而在某些情况下,如果我们需要Map集合里的元素有序,那么HashMap是不能满足我们的要求的。 那么有没有有序Map集合呢?有,Java提供了两种有序Map集合:LinkedHashMap和TreeM...
  • Key有序Map

    千次阅读 2016-01-20 11:35:12
    java map key排序
  • Map有序转成有序json

    千次阅读 2020-03-31 16:58:20
    Map有序转成有序json 项目里要对一些签名的请求值签名,后台来验签,本来的是使用一些特殊的方法直接序列化的,下面给出例子。后来使用自定义的签名方法,得要自己序列化,以便于和后台验签方法一致。 之前的Map序列...
  • Golang map有序

    千次阅读 2018-10-24 10:02:16
    要使得Map有序化,我们必须要对map的key进行排序,我们可以使用sort.Strings函数对字符串进行排序。 package main import ( "fmt" "sort" ) func main() { slice1 := map[string]int{ &...
  • Activity 间intent传递有序排序的map集合 intent传递map排序
  • Map有序存储数据

    万次阅读 2015-08-27 14:22:44
    我们知道 Map存储数据的时候是无序的。而有的时候,我们按照自己的顺序进行排序。譬如:你查询出一个集合数据,往map里塞数据的时候,想要按照自己查询时的数据顺序进行排序。那么我们就不能用常规的map来操作数据。...
  • 有序map LinkedHashMap

    万次阅读 2015-08-28 17:51:54
    Map.Entry e = (Map.Entry) it.next(); System.out.println("Key: " + e.getKey() + "; Value: " + e.getValue()); } } // 有序(默认排序,不能指定) public static void hasOrder() { System.out....
  • Map的遍历和Map有序和无序

    万次阅读 2018-03-16 14:02:26
    另:HashMap是无序的 Map&lt;String, List&lt;Integer&gt;&gt; listMap = new ...//有序Map&lt;Integer, String&gt; map = new HashMap&lt;Integer, String&gt;(); 8 ...
  • 有序Map集合--LinkedHashMap

    万次阅读 2019-03-19 15:37:44
    由于map集合时无序的,我们接触到最多的集合中只有List集合时有序的.通过查了查,发现有一种map(LinkedHashMap)集合时有序的,可以做到按照用户放入集合的顺序取出集合中的元素. LinkedHashMap介绍: 简单的介绍...
  • Map有序

    千次阅读 2019-08-23 15:00:36
    TreeMap提供了一种完全不同的Map实现.TreeMap有着比HashMap更为强大的功能,实现了SortedMap接口.TreeMap的迭代输出将会以元素顺序进行.TreeMap的排序则根据元素的key进行排序,是基于元素的固有顺序(由Comparator或者...
  • 实现key有序MAP

    千次阅读 2014-09-01 13:26:24
    有序可以用List,要便于查找可以用Map,那既要有序又便于查找呢?  最近我就遇到了这样一个问题,Java没有给我们提供现成的类,我们完全可以自己开发个类继承List和Map(Java原来就有不可以同时继承List和...
  • map有序排放

    2016-07-12 18:39:34
    Map如果想要有序的话,需要应用LinkedHashMap
  • java 有序Map LinkedHashMap简介

    万次阅读 2019-09-06 15:21:59
    无序的HashMap 我们知道HashMap是无需的,数据并不是按我们插入的顺序排序的,我们可以验证下 public class Test6 { ... Map<String, String> hashMap = new HashMap<String, String>()...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 147,024
精华内容 58,809
关键字:

有序的map