如何用C语言实现手写数组、链表和红黑树组成的Map结构？

本文共计3371个文字，预计阅读时间需要14分钟。

目录+要求+结构+红黑树和链表转换策略+hash+使用+要求+需要准备数组集合（List）+数据结构+要求+需要准备单向链表（Linked）+数据结构+要求+需要准备红黑树（Rbtree）数据结构+要求+需要准备红黑树和链表适配策略+

目录

• 要求
• 结构
• 红黑树和链表转换策略
• hash
• 使用

要求

需要准备数组集合(List) 数据结构

需要准备单向链表(Linked) 数据结构

需要准备红黑树(Rbtree)数据结构

需要准备红黑树和链表适配策略(文章内部提供,可以自行参考)

建议先去阅读我博客这篇文章C语言-手写Map(数组+链表)(全功能) 有助于理解

hashmap使用红黑树的原因是： 当某个节点值过多的时候那么链表就会非常长,这样搜索的时候查询速度就是O(N) 线性查询了,为了避免这个问题我们使用了红黑树,当链表长度大于8的时候我们转换为红黑树,当红黑树的长度小于6的时候转换为链表,这样既可以利用链表对内存的使用率而且还可以使用红黑树的高效检索，是一种很有效率的数据结构。