cmap

Documentation

Index

• Constants
• func BKDRHash(str string) uint64
• type Bucket
• type BucketStatus
• type ConcurrentMap
  • func NewConcurrentMap(concurrency int, pairRedistributor PairRedistributor) (ConcurrentMap, error)
• type ConcurrentMapImpl
  • func (c *ConcurrentMapImpl) Concurrency() int
  • func (c *ConcurrentMapImpl) Delete(key string) bool
  • func (c *ConcurrentMapImpl) Get(key string) interface{}
  • func (c *ConcurrentMapImpl) Len() uint64
  • func (c *ConcurrentMapImpl) Put(key string, element interface{}) (bool, error)
• type Pair
• type PairRedistributor
• type PairRedistributorImpl
  • func (pr *PairRedistributorImpl) CheckBucketStatus(pairTotal uint64, bucketSize uint64) (bucketStatus BucketStatus)
  • func (pr *PairRedistributorImpl) Redistribute(bucketStatus BucketStatus, buckets []Bucket) (newBuckets []Bucket, changed bool)
  • func (pr *PairRedistributorImpl) UpdateThreshold(pairTotal uint64, bucketNumber int)
• type Segment

Constants

const (
	// DEFAULT_BUCKET_LOAD_FACTOR 默认的装载因子
	// 当散列段中的某个散列桶的尺寸超过了
	// 本因子与当散列段尺寸的乘积，就会触发 rehash
	DEFAULT_BUCKET_LOAD_FACTOR float64 = 0.75
	// DEFAULT_BUCKET_NUMBER 一个散列段包含 bucket 的默认数量
	DEFAULT_BUCKET_NUMBER int = 16
	// DEFAULT_BUCKET_MAX_SIZE 单个 bucket 的默认最大尺寸
	DEFAULT_BUCKET_MAX_SIZE uint64 = 1000
)

const (
	ERROR_PACKAGE_CMAP        = "cmap"
	ERROR_TYPE_ILLEGAL_PARAMS = "illegal parameter"
	ERROR_TYPE_ILLEGAL_PAIR   = "illegal pair type"
)

const (
	// MAX_CONCURRENCY 代表最大并发量
	MAX_CONCURRENCY int = 65536
)

Functions

func BKDRHash

func BKDRHash(str string) uint64

for test

Types

type Bucket

type Bucket interface {
	// Put 会放入一个键-元素对
	// 第一个返回值表示是否新增了键-元素对
	// 若在调用此方法前已经锁定 lock，则不要把 lock 传入！否则必须传入对应的 lock
	Put(p Pair, lock sync.Locker) (bool, error)
	// Get 会获取指定键的键-元素对。
	Get(key string) Pair
	// GetFirstPair 会返回第一个键-元素对
	GetFirstPair() Pair
	// Delete 会删除指定的键-元素对
	// 若在调用此方法前已经锁定 lock，则不要把 lock 传入！否则必须传入对应的 lock
	Delete(key string, lock sync.Locker) bool
	// Clear 会清空当前散列桶。
	// 若在调用此方法前已经锁定 lock，则不要把 lock 传入！否则必须传入对应的 lock
	Clear(lock sync.Locker)
	// Size 会返回当前散列桶的尺寸
	Size() uint64
	// String 会返回当前散列桶的字符串表示形式
	String() string
}

type BucketStatus

type BucketStatus uint8

BucketStatus 代表散列桶状态的类型

const (
	// BUCKET_STATUS_NORMAL 代表散列桶正常
	BUCKET_STATUS_NORMAL BucketStatus = iota
	// BUCKET_STATUS_UNDERWEIGHT 代表散列桶过轻
	BUCKET_STATUS_UNDERWEIGHT
	// BUCKET_STATUS_OVERWEIGHT 代表散列桶过重
	BUCKET_STATUS_OVERWEIGHT
)

type ConcurrentMap

type ConcurrentMap interface {
	// 返回并发量
	Concurrency() int
	Put(key string, element interface{}) (bool, error)
	Get(key string) interface{}
	Delete(key string) bool
	Len() uint64
}

func NewConcurrentMap

func NewConcurrentMap(concurrency int, pairRedistributor PairRedistributor) (ConcurrentMap, error)

type ConcurrentMapImpl

type ConcurrentMapImpl struct {
	// contains filtered or unexported fields
}

concurrency 并发量，也代表了 segments 的长度 散列段，每个散列段要提供对其包含的键值对的读写操作，通过锁来保证并发安全性。 多个散列段就由多个互斥锁保护。这样的加锁方式叫做 "分段锁"。分段锁可以降低互斥锁带来的开销，同时保护资源。 因为同一时刻同一个散列段中的键值对只能被一个 goroutine 进行读写。但是不同的散列段可以并发访问。 如果 concurrency 为 16，那么就可以有 16 个 goroutine 并发访问 ConcurrentMap。

func (*ConcurrentMapImpl) Concurrency

func (c *ConcurrentMapImpl) Concurrency() int

func (*ConcurrentMapImpl) Delete

func (c *ConcurrentMapImpl) Delete(key string) bool

func (*ConcurrentMapImpl) Get

func (c *ConcurrentMapImpl) Get(key string) interface{}

func (*ConcurrentMapImpl) Len

func (c *ConcurrentMapImpl) Len() uint64

func (*ConcurrentMapImpl) Put

func (c *ConcurrentMapImpl) Put(key string, element interface{}) (bool, error)

type Pair

type Pair interface {

	// Key 会返回 key
	Key() string
	// Hash 会返回 key hash
	Hash() uint64
	// Element 会返回 element
	Element() interface{}
	// Set 会设置元素的值
	SetElement(element interface{}) error
	// Copy 会生成一个当前键-元素对的副本并返回
	Copy() Pair
	// String 会返回当前键-元素对的字符串表示形式
	String() string
	// contains filtered or unexported methods
}

Pair 代表并发安全的键-元素对的接口

type PairRedistributor

type PairRedistributor interface {
	//  UpdateThreshold 会根据键-元素对总数和散列桶总数计算并更新阈值
	UpdateThreshold(pairTotal uint64, bucketNumber int)
	// CheckBucketStatus 用于检查散列桶的状态。
	CheckBucketStatus(pairTotal uint64, bucketSize uint64) (bucketStatus BucketStatus)
	// Redistribute 用于实施键-元素对的再分布。
	Redistribute(bucketStatus BucketStatus, buckets []Bucket) (newBuckets []Bucket, changed bool)
}

PairRedistributor 代表针对键-元素对的再分布器 用于当散列段内的键-元素对分布不均时进行重新分布

type PairRedistributorImpl

type PairRedistributorImpl struct {
	// contains filtered or unexported fields
}

func (*PairRedistributorImpl) CheckBucketStatus

func (pr *PairRedistributorImpl) CheckBucketStatus(
	pairTotal uint64, bucketSize uint64) (bucketStatus BucketStatus)

func (*PairRedistributorImpl) Redistribute

func (pr *PairRedistributorImpl) Redistribute(
	bucketStatus BucketStatus, buckets []Bucket) (newBuckets []Bucket, changed bool)

func (*PairRedistributorImpl) UpdateThreshold

func (pr *PairRedistributorImpl) UpdateThreshold(
	pairTotal uint64, bucketNumber int)

type Segment

type Segment interface {
	// Put 会根据参数放入一个键-元素对
	// 第一个返回值表示是否新增了键-元素对
	Put(p Pair) (bool, error)
	// Get 会根据给定参数返回对应的键-元素对
	// 该方法会根据给定的键计算哈希值
	Get(key string) Pair
	// GetWithHash 会根据给定参数返回对应的键-元素对，为了避免重复计算 hash
	// 注意！参数 keyHash 应该是基于参数 key 计算得出哈希值
	GetWithHash(key string, keyHash uint64) Pair
	// Delete 会删除指定键的键-元素对
	// 若返回值为true则说明已删除，否则说明未找到该键
	Delete(key string) bool
	// Size 用于获取当前段的尺寸（其中包含的散列桶的数量）
	Size() uint64
}

Segment 代表并发安全的散列段的接口