Реализация карты - Запах кода в Lookup () и Insert ()

Question

Ниже приведен код реализации карты с использованием массива, фрагмента и указателей:

package gomap

import "fmt"

type Entry struct {
    stockName  string
    stockValue float64
}

type bucket []Entry

type Map [4]bucket

type bucketElementPosition [4]int

var emptyPosition = bucketElementPosition{0, 0, 0, 0}

func Newmap() Map {

    return Map{} // [(nil,0,0), (nil,0,0), (nil,0,0), (nil,0,0)]
}

func (m *Map) Lookup(key string) float64 {

    bucketNumber := (key[0] - 'A') / 7
    for _, entry := range m[bucketNumber] { // (*m)[bucketNumber]
        if entry.stockName == key {
            return entry.stockValue
        }
    }
    return 0
}

func (m *Map) Insert(key string, value float64) {

    bucketNumber := (key[0] - 'A') / 7

    if cap(m[bucketNumber]) == 0 { // (*m)[bucketNumber]
        fmt.Println("bucket number:", bucketNumber)
        m[bucketNumber] = make([]Entry, 0, 100)
    }

    m[bucketNumber] = append(m[bucketNumber], Entry{key, value})
    emptyPosition[bucketNumber]++
}

---

package main

import (
    "fmt"

    "github.com/myhub/cs61a/gomap"
)

func main() {

    var stockData = gomap.Newmap()


    (&stockData).Insert("AAPL", 94.56)
    (&stockData).Insert("HSCO", 26.72)
    (&stockData).Insert("NMZN", 697.45)
    (&stockData).Insert("ZSFT", 50.81)
    (&stockData).Insert("PMGN", 150.83)

    fmt.Println((&stockData).Lookup("AAPL"))
    fmt.Println((&stockData).Lookup("HSCO"))
    fmt.Println((&stockData).Lookup("NMZN"))
    fmt.Println((&stockData).Lookup("ZSFT"))
    fmt.Println((&stockData).Lookup("PMGN"))

}

---

Запах кода bucketNumber := (key[0] - 'A') / 7 можно устранить, считая биты и га sh .

а по линии type bucket []Entry

Как сделать бетон типа Map, Entry типа агности c? потому что ключ зафиксирован как string, а значение зафиксировано как float64

Answer 1

Я выполнил домашнее задание так:

package gomap

import "fmt"

type Entry struct {
    key, value interface{}
}

type Map struct {
    buckets [4][]Entry
}

func Newmap() *Map {
    return &Map{}
}

func (m *Map) bucketNumber(key interface{}) int {
    s := fmt.Sprint(key)
    return int(s[0]) % len(m.buckets)
}

func (m *Map) Lookup(key interface{}) interface{} {
    bucketNumber := m.bucketNumber(key)
    for _, entry := range m.buckets[bucketNumber] {
        if entry.key == key {
            return entry.value
        }
    }
    return nil
}

func (m *Map) Insert(key interface{}, value interface{}) {
    bucketNumber := m.bucketNumber(key)
    m.buckets[bucketNumber] = append(m.buckets[bucketNumber], Entry{key, value})
}

https://play.golang.org/p/KmVSeDavc3y

Answer 2

Есть несколько способов сделать это. Наиболее очевидным является использование интерфейса {} для ключа и значения. Тем не менее, существует безопасный для ключей способ создания ключей. Вы можете сделать Key интерфейсом:

type Key interface {
   // Returns the bucket number for the key
   BucketNumber() int
   // Eq compares the key with the given key
   Eq(Key) bool
}

. Затем вы можете получить запись, используя эту клавишу:

type Entry struct {
    k Key
    v interface{}
}

. Вы можете переписать функции карты, чтобы использовать эту клавишу. Значение должно быть интерфейсом, и вы должны использовать утверждения типа, чтобы получить базовое значение.