Go/encoding/json · map 编码

按键排序后编码 JSON 对象

Go 的 JSON 编码器先收集 map 的键值，再用 PDQsort 按键名排序，避免直接沿用 map 的遍历顺序。

go1.23.0检索与计算核验 2026-10-12

工程问题#

Go map 的遍历顺序不固定。编码 JSON 对象时，需要按照转换后的字符串键组织输出，同时处理大小不同、原本有序或分布不均的键集合。

实际实现#

mapEncoder.encode 将键转换为字符串并收集值，调用 slices.SortFunc 按字符串比较排序。go1.23.0 的 SortFunc 使用 pattern-defeating quicksort：以枢轴划分区间，小区间转插入排序，过多不平衡划分后转堆排序。

处理流程#

把 map 的键转换为 JSON 键名，保存键值对
按键名调用 slices.SortFunc，进入 PDQsort
划分并递归处理较短区间；小区间及退化输入走相应回退
按排序结果逐个输出键和值

源码片段#

固定版本 · 原文摘录

src/encoding/json/encode.gogo1.23.0 · L750–L764

查看原文件

750	// Extract and sort the keys.751	var (752		sv  = make([]reflectWithString, v.Len())753		mi  = v.MapRange()754		err error755	)756	for i := 0; mi.Next(); i++ {757		if sv[i].ks, err = resolveKeyName(mi.Key()); err != nil {758			e.error(fmt.Errorf("json: encoding error for type %q: %q", v.Type().String(), err.Error()))759		}760		sv[i].v = mi.Value()761	}762	slices.SortFunc(sv, func(i, j reflectWithString) int {763		return strings.Compare(i.ks, j.ks)764	})

mapEncoder.encode → slices.SortFunc

JSON 编码器收集转换后的字符串键和对应值，再按键名排序；下方循环按排序结果编码成员。

GOBSD-3-Clause

src/slices/sort.gogo1.23.0 · L21–L33

查看原文件

21// SortFunc sorts the slice x in ascending order as determined by the cmp22// function. This sort is not guaranteed to be stable.23// cmp(a, b) should return a negative number when a < b, a positive number when24// a > b and zero when a == b or a and b are incomparable in the sense of25// a strict weak ordering.26//27// SortFunc requires that cmp is a strict weak ordering.28// See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings.29// The function should return 0 for incomparable items.30func SortFunc[S ~[]E, E any](x S, cmp func(a, b E) int) {31	n := len(x)32	pdqsortCmpFunc(x, 0, n, bits.Len(uint(n)), cmp)33}

slices.SortFunc

SortFunc 明确是不稳定排序，实际分派到 pdqsortCmpFunc，limit 取输入长度的位数。

GOBSD-3-Clause

src/slices/zsortanyfunc.gogo1.23.0 · L61–L81

查看原文件

61func pdqsortCmpFunc[E any](data []E, a, b, limit int, cmp func(a, b E) int) {62	const maxInsertion = 126364	var (65		wasBalanced    = true // whether the last partitioning was reasonably balanced66		wasPartitioned = true // whether the slice was already partitioned67	)6869	for {70		length := b - a7172		if length <= maxInsertion {73			insertionSortCmpFunc(data, a, b, cmp)74			return75		}7677		// Fall back to heapsort if too many bad choices were made.78		if limit == 0 {79			heapSortCmpFunc(data, a, b, cmp)80			return81		}

pdqsortCmpFunc：短区间与退化回退

长度不超过 12 时调用插入排序；坏划分预算耗尽时调用堆排序。这是快速排序的工程变体。

GOBSD-3-Clause

src/slices/zsortanyfunc.gogo1.23.0 · L106–L127

查看原文件

106		// Probably the slice contains many duplicate elements, partition the slice into107		// elements equal to and elements greater than the pivot.108		if a > 0 && !(cmp(data[a-1], data[pivot]) < 0) {109			mid := partitionEqualCmpFunc(data, a, b, pivot, cmp)110			a = mid111			continue112		}113114		mid, alreadyPartitioned := partitionCmpFunc(data, a, b, pivot, cmp)115		wasPartitioned = alreadyPartitioned116117		leftLen, rightLen := mid-a, b-mid118		balanceThreshold := length / 8119		if leftLen < rightLen {120			wasBalanced = leftLen >= balanceThreshold121			pdqsortCmpFunc(data, a, mid, limit, cmp)122			a = mid + 1123		} else {124			wasBalanced = rightLen >= balanceThreshold125			pdqsortCmpFunc(data, mid+1, b, limit, cmp)126			b = mid127		}