2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
map kv प्रारूपेण कील-मूल्ययुग्मानां अक्रमितसङ्ग्रहः अस्ति
var name map[key_type]value_type
// 方式一
var m map[int]string = map[int]string{}
// 方式二
m := map[int]string{
1 : "老一",
2 : "老二",
3 : "老三",
}
// 方式三：5代表容量，也就是在内存中占用多大的空间，可以省略
m := make(map[int]string,5)
mapName[key] = value
// 假设map名为m，key为int，value为string
m[5] = "老五"
कील-आधारित-तत्त्वानि विलोपयन्तु, अस्तित्वहीन-कील-विलोपनसमये कोऽपि दोषः न निवेदितः भविष्यति ।
delete(mapName, key)
// 假设map名为m，key为int，value为string
delete(m, 5)
परिवर्तनार्थं निर्दिष्टकुंजीसम्बद्धं मूल्यं प्रत्यक्षतया परिवर्तयितुं शक्नुवन्ति ।
mapName[key] = newValue
// 假设map名为m，key为int，value为string
m[5] = "五"
कीलस्य अनुसारं मूल्यं प्राप्नुवन्तु, ठीकम् अस्ति ध्वजबिट् अस्ति वा तत् प्राप्तम् अस्ति वा, प्रकारः Boolean अस्ति
यदि मूल्यं न लभ्यते तर्हि कोऽपि दोषः न निवेदितः भविष्यति तथा च तत्सम्बद्धप्रकारस्य शून्यमूल्यं प्रत्यागमिष्यति ।
value, ok := mapName[key]
if !ok {
fmt.Println(ok)
}
नोटः- नक्शा-भ्रमणम् अक्रमितम् अस्ति
for key, value := range myMap {
// 处理每对键值
}
// 例子
for i, s := range m {
fmt.Println(i, s)
}
गोलाङ्गभाषायां नक्शायाः अन्तर्निहितः सारः उपयोगः एव
hashmapकार्यान्वितम् अस्ति, अतः नक्शा मूलतः अस्ति哈希表。
哈希表इति प्रयोगः哈希函数दत्तांशं दत्तांशसंरचनेषु व्यवस्थितं कुर्वन्तु ये द्रुतप्रवेशं अन्वेषणं च समर्थयन्ति।
哈希函数, यत् हैश फंक्शन् इति अपि ज्ञायते, तत् एकं फंक्शन् अस्ति यत् विशिष्टस्य हैश एल्गोरिदम् इत्यस्य माध्यमेन कस्यापि दीर्घतायाः (यथा स्ट्रिंग्) निवेशं नियत-दीर्घतायाः आउटपुट् मध्ये परिवर्तयति हैशमूल्यानां अभिगमनप्रदर्शनं सुनिश्चित्य प्रायः हैशमूल्यानि सरणीरूपे संगृह्यन्ते ।
यदि निवेशस्य परिधिः नक्शाङ्कितस्य निर्गमस्य परिधिं अतिक्रमति तर्हि भिन्न-भिन्न-निवेशानां समानं निर्गमं प्राप्तुं शक्नोति
哈希冲突。प्रायः एतस्याः समस्यायाः समाधानार्थं द्वौ उपायौ स्तः ।
开放地址法तथा拉链法
मुक्तसङ्केतविधिः : १.
दत्तांशसंरचनानि प्रायः सरणीनां उपयोगेन कार्यान्विताः भवन्ति
अभावः : १.
अस्मिन् उपाये विग्रहाणां समाधानार्थं अधिकं स्थानस्य आवश्यकता भवति यतोहि न केवलं दत्तांशः संगृहीतः भवति, अपितु टकरावस्य समाधानार्थं अतिरिक्तस्थानं आवश्यकं भवति ।
जिपर-विधिः (go language map इत्यनेन एषा पद्धतिः उपयुज्यते):
सरणीः, लिङ्क्ड् सूचीः च प्रायः अन्तर्निहितदत्तांशसंरचनारूपेण उपयुज्यन्ते
सरणीयाः विभिन्नेषु अनुक्रमणिकासु लिङ्क् कृतं लिङ्क् कृतं सूचीं बकेट् इति अपि उच्यते ।
type hmap struct {
count int // 当前哈希表中的元素数量，即键值对数量，可用内置函数len()获取
flags uint8 // 标志位，标记map状态和属性的字段，如正在迭代等状态
B uint8 // 表示哈希表桶（buckets）的数量为2的B次方
noverflow uint16 // 溢出桶的大致数量，扩容时会用到
hash0 uint32 // 哈希种子，对key做哈希是加入种子计算哈希值，确保map安全性
buckets unsafe.Pointer // 存储桶数组的指针
oldbuckets unsafe.Pointer // 扩容时用于保存旧桶数组的指针 , 大小为新桶数组的一半
nevacuate uintptr // 扩容时的迁移进度器，迁移桶下标小于此值说明完成迁移
extra *mapextra // 溢出桶的指针，指向mapextra结构体，用于存储一些额外的字段和信息
}
// mapextra 处理桶溢出的结构体
type mapextra struct {
overflow *[]*bmap // 溢出桶数组指针，仅当key和elem非指针时才使用
oldoverflow *[]*bmap // 旧的溢出桶数组指针，仅当key和elem非指针时才使用
nextOverflow *bmap // 下一个可用的溢出桶地址
}
स्रोतसङ्केते bmap प्रकारस्य केवलं एकं tophash क्षेत्रं भवति ।परन्तु संकलनस्य समये Go संकलकः स्वयमेव उपयोक्तृसङ्केतस्य अनुसारं तत्सम्बद्धान् कीलम्, मूल्यम् अन्यसंरचनानि च इन्जेक्ट् करिष्यति ।
पृष्ठीय bmap
type bmap struct {
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
tophash [bucketCnt]uint8
// Followed by bucketCnt keys and then bucketCnt elems.
// NOTE: packing all the keys together and then all the elems together makes the
// code a bit more complicated than alternating key/elem/key/elem/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
वास्तविक bmap
// 编译期间会动态地创建一个新的结构：
type bmap struct {
topbits [8]uint8 // 这里存储哈希值的高八位，用于在确定key的时候快速试错，加快增删改查寻址效率,有时候也叫tophash
keys [8]keytype // 存储key的数组，这里bmap最多存储8个键值对
elems [8]valuetype // 存储value的数组，这里bmap也最多存储8个键值对
...
overflow uintptr // 溢出桶指针
}
Go भाषायां नक्शाप्रदर्शनं निर्वाहयितुम् स्वयमेव नक्शाविस्तारः क्रियते ।
प्रथमं लेखनकाले नक्शा उत्तीर्णः भवतिruntime.mapassignविस्तारस्य आवश्यकता अस्ति वा इति निर्धारयन्तु
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing.
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again // Growing the table invalidates everything, so try again
}
...
}
// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B > 15 {
B = 15
}
return noverflow >= uint16(1)<<(B&15)
}
उपर्युक्तसंहितानुसारं विस्तारस्य न्यायार्थं द्वौ शर्तौ स्तः- १.
overLoadFactor(h.count+1, h.B) , भारगुणकः = तत्त्वानां संख्या ÷ बाल्टीनां संख्याtooManyOverflowBuckets(h.noverflow, h.B))विस्तारविधिः : १.
यदा भारकारकः अतिबृहत् भवति तदा नूतनं लोटादीर्घता मूलदीर्घतायाः द्विगुणं भवति, ततः पुरातनं बाल्टीदत्तांशं नूतनबाल्टीं प्रति स्थानान्तरितम् अस्ति ।
तत्र बहु दत्तांशः नास्ति, परन्तु अतिप्रवाहलोटाः सन्ति ।विस्तारस्य समये, बाल्टीनां संख्या अपरिवर्तिता एव तिष्ठति, वृद्धिशीलविस्तारसदृशानि स्थानान्तरणक्रियाः पुनः क्रियन्ते, तथा च बाल्टी-उपयोगं वर्धयितुं द्रुततरं प्रवेशं सुनिश्चित्य शिथिल-की-मूल्ययुग्मानि पुनः व्यवस्थितानि भवन्ति
विस्तारपदार्थाः : १.
func hashGrow(t *maptype, h *hmap) {
...
// 原有桶设置给oldbuckets
oldbuckets := h.buckets
// 创建新桶
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// commit the grow (atomic wrt gc)
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
h.nevacuate = 0
h.noverflow = 0
...
}
// 这个是mapdelete函数中的处理迁移的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
if h.growing() {
//
growWork(t, h, bucket)
}
...
}
渐进式驱逐 कील-मूल्ययुग्मानि प्रवासयन्तु। अस्य अर्थः अस्ति यत् विस्तारस्य समये पुरातनः बाल्टी-सरणयः नूतनः बाल्टी-सरणयः च एकस्मिन् समये विद्यन्ते, नवनिवेशितानि कील-मूल्ययुग्मानि प्रत्यक्षतया नूतन-बाल्टी-मध्ये स्थापितानि भविष्यन्ति, पुरातन-बाल्टी-सरणौ प्रवासन-क्रियाम् आरभते// 进入后是一个简单的判断，之后的evacuate是核心逻辑处理，特别多，感兴趣自己看源码
func growWork(t *maptype, h *hmap, bucket uintptr) {
// make sure we evacuate the oldbucket corresponding
// to the bucket we're about to use
evacuate(t, h, bucket&h.oldbucketmask())
// evacuate one more oldbucket to make progress on growing
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
intवाint64。sync.Mapअथवा स्वस्य समवर्ती सुरक्षितं मानचित्रं कार्यान्वयन्तु।
सः ३० वर्षाणाम् अधिकं कालात् प्रौद्योगिक्याः शोधकार्यं कर्तुं समर्पितः अस्ति, तथा च जावा, लिनक्स, जावास्क्रिप्ट्, php, css इत्यादिषु विविधभाषासु प्रवीणः अस्ति, मुक्तस्रोतक्षेत्रे सः बहु योगदानं कृतवान् अस्ति विकासक दस्तावेजीकरणस्थानकं भविष्ये सन्दर्भार्थं प्रौद्योगिकीविकासे केचन विषयाः साझां कर्तुं सर्वे तत् पश्यन्तु
