联系昆明网站建设,客户网站分析,wordpress tag调用,中国装修公司排行榜树
树是一种由 n 个有限节点组成的具有层次关系的集合。
树的定义#xff1a;
节点之间有层次关系#xff0c;分为父节点和子节点有唯一一个的根节点#xff0c;该节点没有父节点除了根节点#xff0c;每个节点有且只有一个父节点每一个节点本身以及它的后代也是一棵树
节点之间有层次关系分为父节点和子节点有唯一一个的根节点该节点没有父节点除了根节点每个节点有且只有一个父节点每一个节点本身以及它的后代也是一棵树是一个递归结构没有后代的节点成为叶子节点没有节点的树称为空树
二叉树每个节点最多只有两个儿子节点的树
满二叉树叶子节点与叶子节点之间的高度差为 0 的二叉树。即整棵树是满的。树形呈现出满三角形结构。
完全二叉树完全二叉树是由满二叉树而引出来的。这里我们设二叉树的深度为 k除了第 k 层以外其他各层节点树都达到了最大值且第 k 层所有的节点都连续集中在最左侧。
树常见的数学特征
高度为 h 的二叉树至少 h 1 个节点高度为 h 的二叉树至少 2 ^ h 1 个节点含有 n 个节点的二叉树的高度至多为 n - 1含有 n 个节点的二叉树的高度至少为 log n在二叉树的第 i 层至多有 2 ^ (i - 1) 个节点
链表实现二叉树
// TreeNode is a tree node
type TreeNode struct {Data string // dataLeft *TreeNode // left childRight *TreeNode // right child
}当然了我们也可以使用 数组 来表示二叉树但是一般用来表示完全二叉树。
对于一棵有 n 个节点的完全二叉树从上到下从左到右进行序号编号对于一个任意节点编号 i 0表示树根节点编号 i 的节点的左右儿子节点编号分别是2 * i 2 * i 1, 父节点的编号为 i / 2。
树的遍历
对于一棵树的遍历我们有如下四种遍历方法
先序遍历先访问根节点再访问左子树最后访问右子树后序遍历先访问左子树再访问右子树最后访问根节点中序遍历先访问左子树再访问根节点最后访问右子树层序遍历每一层从左到右地访问每一个节点
实现树的前三种遍历打印结果
// PreOrder 先序遍历 根左右
func PreOrder(tree *Node) {if tree nil {return}fmt.Println(tree.Data, )PreOrder(tree.Left)PreOrder(tree.Right)
}// MidOrder 中序遍历 左根右
func MidOrder(tree *Node) {if tree nil {return}MidOrder(tree.Left)fmt.Println(tree.Data, )MidOrder(tree.Right)
}// PostOrder 后续遍历 左右根
func PostOrder(tree *Node) {if tree nil {return}PostOrder(tree.Left)PostOrder(tree.Right)fmt.Println(tree.Data, )
}在实现树的层序遍历的时候我们一般会使用队列作为辅助数据结构来实现。
首先将树的树根节点放入到队列中。从队列中 Remove 出节点先打印节点值如果该节点有左子树左子树入队如果该节点有右子树右子树入队。重复2直到队列中再无其他元素。
在实现之前我们先实现一些辅助函数此处的函数是基于我们上一次的链式队列的修改。
// LinkNode 定义链表节点
type LinkNode struct {Next *LinkNodeValue *Node
}// LinkQueue 定义链表队列
type LinkQueue struct {root *LinkNodesize intlock sync.Mutex
}// Add 入队
func (q *LinkQueue) Add(v *Node) {q.lock.Lock()defer q.lock.Unlock()// 如果队列为空我们将新节点作为队列的根节点if q.root nil {q.root new(LinkNode)q.root.Value v} else {// 队列不为空新建一个节点采用尾插法实现newNode : new(LinkNode)newNode.Value v// 找到尾节点nowNode : q.rootif nowNode.Next ! nil {nowNode nowNode.Next}nowNode.Next newNode}q.size
}// Remove 出队
func (q *LinkQueue) Remove() *Node {q.lock.Lock()defer q.lock.Unlock()if q.size 0 {return nil}// 找到队头节点top : q.rootv : top.Value// 将对头元素出队q.root top.Nextq.size--return v
}// Size 队列大小
func (q *LinkQueue) Size() int {return q.size
}接下来实现我们的层序遍历
// LayerOrder 层序遍历
func LayerOrder(tree *Node) {if tree nil {return}// 借助队列实现层序遍历queue : new(LinkQueue)// 将根节点入队queue.Add(tree)// 层序遍历for queue.Size() 0 {// 获取队列头元素element : queue.Remove()// 输出fmt.Println(element.Data, )// 将左右子树入队if element.Left ! nil {queue.Add(element.Left)}if element.Right ! nil {queue.Add(element.Right)}}
}哈希表
首先我们来理清楚些概念
线性查找
线性查找也被称作顺序查找是一种非常基础且直观的查找算法。顾名思义线性查找会按照顺序查找数据直到找到所需要的数据为止。
线性查找的步骤如下
从数据集合的第一个元素开始。将当前元素与所查找的目标元素进行比较。如果当前元素和目标元素相等那么返回当前元素的位置查找结束。如果当前元素和目标元素不相等则继续检查下一个元素。如果已经检查完所有元素但还没有找到目标元素那么返回一个表示“未找到”的结果。
线性查找的优势在于它不需要预先对数据进行排序这在一些需要频繁插入和删除的场景中会非常有用。此外对于较小的数据集线性查找是足够有效的。
但是对于大规模数据集线性查找的效率并不高因为在最坏的情况下线性查找可能需要检查集合中的每一个元素。
散列查找
哈希查找也称为散列查找是一种使用哈希哈希表存储数据通过哈希函数快速查找数据的方法。
散列查找的步骤如下
选择一个哈希函数哈希函数会接受一个输入或者叫键并返回一个整数这个整数就是在哈希表中存放数据的位置。创建哈希表创建一个可以存放数据的哈希表通常是一个数组。大小可以视实际情况而定。插入数据当你有一份数据需要插入哈希表时会把这份数据的键放入哈希函数得到一个哈希值然后把数据存放到这个哈希值对应的位置。查找数据当你需要查找一份数据时也是把这份数据的键放入哈希函数得到一个哈希值然后去这个哈希值对应的位置取出数据。由于哈希值的计算速度非常快所以查找的速度也非常快。
虽然散列查找的速度很快。但是在实际应用中还需要处理一些复杂的问题如碰撞问题。当两个键的哈希值相同这称为哈希碰撞就需要有一种方法来处理最常见的处理方法包括开放寻址法和链地址法。
接下来我们将已经引入开放寻址法和链地址法。
开放寻址法
开放寻址法是解决哈希冲突的一种方法。它的基本思想是如果哈希函数返回的位置已经有数据了即发生了冲突那么就从当前位置起依据某种探查规则在哈希表中找到另一个位置直到找到一个空的位置或者达到查找上限。
常见的探查规则有以下三种
线性探查线性探查的步骤是如果哈希函数返回的位置已经有数据了就顺序往下查找直到找到一个空的位置。比如初始位置是 i 那么就依次查找 i1 , i2 , i3 …直到找到空的位置。这种方法简单但可能导致数据在哈希表中的分布不均匀产生一种叫做“聚集”的现象。二次探查二次探查的步骤是如果哈希函数返回的位置已经有数据了那么就按照平方的规则往下查找直到找到一个空的位置。比如初始位置是i那么就依次查找i1², i2², i3²…直到找到空的位置。这种方法相对于线性探查能更好地防止聚集问题。双重哈希双重哈希的步骤是使用一个额外的哈希函数来解决哈希冲突。比如初始哈希函数返回位置 i 如果 i 位置已经有数据了那么就按照另一个哈希函数的规则进行探查直到找到一个空的位置。这种方法可以避免聚集但需要计算额外的哈希函数增加了一些计算复杂性。
开放寻址法的主要优点是实现简单结构紧凑不需要额外的链表或数组结构。缺点是可能会有较差的缓存性能并且需要处理较复杂的删除操作。
链地址法
链地址法也叫做链式哈希是一种用来解决哈希碰撞问题的方法。当哈希函数返回的位置已经有数据了即发生哈希碰撞时链地址法是将这些哈希值相同的元素放到同一个链表中。
链地址法的步骤如下
首先初始化哈希表每个位置都链接到一个链表一开始这些链表都是空的。当我们要插入一个元素时首先计算这个元素的哈希值然后找到对应的链表我们把这个元素插入到链表尾部。当我们要查找一个元素时也是首先计算这个元素的哈希值找到对应的链表然后在链表中进行顺序查找。
链地址法的优点是处理哈希碰撞简单不会出现表满的情况并且在哈希表的大小固定且哈希值分布均匀时查找效果较好。它的缺点是需要额外的存储空间来存放指向链表的指针并且可能存在比较长的链表会降低查找的效率。
哈希函数
哈希函数Hash function是任意长度的输入也叫做预映射pre-image通过散列算法变换成固定长度的输出该输出就是哈希值。
哈希函数的构造规则主要基于以下几个目标
确定性对于同一个输入无论执行多少次哈希函数输出的哈希值始终不变。也就是说如果 ab那么 hash(a)hash(b)。快速计算哈希函数需要能快速地计算出哈希值。给定一个输入进行哈希运算的效率应该很高。雪崩效应即使只是微小的输入变化也会产生巨大的输出变化。换句话说如果 a≠b那么 hash(a) 和 hash(b) 的值应该差别很大。散列均匀哈希函数应该能保证散列值在哈希表中均匀分布避免哈希冲突。
哈希函数在很多不同的场合都有应用例如在数据结构中的哈希表而在密码学中哈希函数通常用来验证数据的完整性比如MD5SHA1SHA2等。
在目前计算哈希速度最快的哈希算法是 xxhash。
说完了一些基础的概念接下来我们来实现一下简单的链式哈希表。
实现链式哈希表
在介绍先介绍一个小知识点防止大家疑惑。
我们在实现时使用到了一个加载因子 factor 这个变量主要用来控制哈希表的扩容与缩容。
我们设定当加载因子 factor 0.125 时进行数组缩容每次将容量对半砍。当加载因子 factor 0.75 进行数组扩容每次将容量翻倍。
定义数据
const (// 扩容因子expandFactor 0.75
)// 键值对
type keyPairs struct {key stringvalue interface{}next *keyPairs
}// HashMap 哈希表
type HashMap struct {array []*keyPairslen intcapacity intcapacityMask intlock sync.Mutex
}初始化
// NewHashMap 初始化哈希表
func NewHashMap(capacity int) *HashMap {// 默认容积为2的幂defaultCapacity : 1 4if capacity defaultCapacity {capacity defaultCapacity} else {capacity 1 int(math.Ceil(math.Log2(float64(capacity))))}// 新建一个哈希表hashtable : new(HashMap)hashtable.capacity capacityhashtable.capacityMask capacity - 1return hashtable
}获取长度
// Len 返回哈希表中键值对的个数
func (hashtable *HashMap) Len() int {return hashtable.len
}计算哈希值
// value 计算哈希值
var value func(key []byte) uint64 {h : xxhash.New()h.Write(key)return h.Sum64()
}获取下标
// hashIndex 计算哈希值并获取下标
func (hashtable *HashMap) hashIndex(key string, mask int) int {// 计算哈希值hash : value([]byte(key))index : hash uint64(mask)return int(index)
}插入元素
// Put 插入键值对
func (hashtable *HashMap) Put(key string, value interface{}) {hashtable.lock.Lock()defer hashtable.lock.Unlock()// 获取下标index : hashtable.hashIndex(key, hashtable.capacityMask)// 此下标在哈希表中的值element : hashtable.array[index]if element nil {// 此下标没有元素则插入hashtable.array[index] keyPairs{key: key,value: value,}} else {// 此下标已经有元素则插入到上一个元素的后面var lastPairs *keyPairsfor element ! nil {if element.key key {element.value valuereturn}lastPairs elementelement element.next}// 找不到元素则插入到最后lastPairs.next keyPairs{key: key,value: value,}}// 长度加一newLen : hashtable.len 1// 计算扩容因子如果长度大于容积的75%则扩容if float64(newLen)/float64(hashtable.capacity) expandFactor {// 新建一个原来两倍大小的哈希表newhashtable : new(HashMap)newhashtable.array make([]*keyPairs, hashtable.capacity*2)newhashtable.capacity hashtable.capacity * 2newhashtable.capacityMask newhashtable.capacity*2 - 1// 遍历原哈希表将元素插入到新哈希表for _, pairs : range hashtable.array {for pairs ! nil {newhashtable.Put(pairs.key, pairs.value)pairs pairs.next}}hashtable.array newhashtable.arrayhashtable.capacity newhashtable.capacityhashtable.capacityMask newhashtable.capacityMask}hashtable.len newLen
}获取元素
// Get 获取键值对
func (hashtable *HashMap) Get(key string) (value interface{}, ok bool) {hashtable.lock.Lock()defer hashtable.lock.Unlock()// 获取下标index : hashtable.hashIndex(key, hashtable.capacityMask)// 此下标在哈希表中的值element : hashtable.array[index]// 遍历元素如果元素的key等于key则返回for element ! nil {if element.key key {return element.value, true}element element.next}return nil, false
}删除元素
// Delete 删除键值对
func (hashtable *HashMap) Delete(key string) {hashtable.lock.Lock()defer hashtable.lock.Unlock()// 获取下标index : hashtable.hashIndex(key, hashtable.capacityMask)// 此下标在哈希表中的值element : hashtable.array[index]// 如果为空链表则直接返回if element nil {return}// 如果第一个元素的key等于key则删除if element.key key {hashtable.array[index] element.nexthashtable.len--return}// 下一个键值对nextElement : element.nextfor nextElement ! nil {if nextElement.key key {element.next nextElement.nexthashtable.len--return}element nextElementnextElement nextElement.next}
}遍历哈希表
// Range 遍历哈希表
func (hashtable *HashMap) Range() {hashtable.lock.Lock()defer hashtable.lock.Unlock()for _, pairs : range hashtable.array {for pairs ! nil {fmt.Println(pairs.key, pairs.value)pairs pairs.next}}fmt.Println(len:, hashtable.len)
}哈希表总结
哈希查找总的来说是一种用空间去换时间的查找算法时间复杂度达到 O ( 1 ) {O(1)} O(1)级别。
总结
本次我们介绍使用Go语言实现数据结构中的树和哈希表并且详细介绍了哈希表的具体实现。数据结构这一系列我们没有涉及到具体的细节的讲解适合有一定数据结构基础的童鞋本系列代码已经上传至Github欢迎大家 Star。
