哈希表和有序表

在 C++ 中，用 unordered_map 替代了 hash_amp。

在 Java 中，基本数据类型 byte, short, int, long, float, double, char, boolean 以及其对应的对象类型如 Integer, String等在哈希表内部按值传递。除此以外按引用传递。

链表

链表结构

单链表：

1
2
3
4
5
6
7
struct ListNode{
  int val;
  ListNode *next;
  ListNode(): val(0), next(nullptr){}
  ListNode(int x) : val(x), next(nullptr){}
  ListNode(int x, ListNode *n) : val(x), next(n){}
};

双向链表：

1
2
3
4
5
6
7
8
struct DoublyListNode{
  int val;
  DoublyListNode *pre;
  DoublyListNode *next;
  DoublyListNode(): val(0), pre(nullptr), next(nullptr){}
  DoublyListNode(int x) : val(x), pre(nullptr), next(nullptr){}
  DoublyListNode(int x, DoublyListNode *p, DoublyListNode *n) : val(x), pre(p), next(n){}
};

单链表逆序

力扣206题

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* reverseList(ListNode* head){
  ListNode *p, *n;
  p = nullptr;
  while(head){
      n = head->next;
      head->next = p;
      p = head;
      head = n;
  }

  return p;
}

双向链表逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
DoublyListNode* reverseList(DoublyListNode* head){
  DoublyListNode *p, *n;
  p = nullptr;
  while(head){
      n = head->next;
      head->next = p;
      head->pre = n;
      p = head;
      head = n;
  }

  return p;
}

哈希表

哈希表的底层实现进阶班讲，此处只讲用法。

HashMap和HashSet的区别：前者有伴随数据（key-value），后者没有伴随数据（只有key），二者底层的实现原理是一样的（key组织的方式）。

哈希表增删改查的时间复杂度是O(1)O(1)，和数据量无关。

java的内存泄漏

源自与变量的游离

举例，假如有一个函数f，它的生存周期很短，调用完就结束了。另有一个map，它的生存周期很长，长到从整个程序开始到结束。在f函数里，new了一个对象z，把z添加到map中去，但是f结束的时候忘记将z从map中remove掉。这就导致z将长期存在，如果f调用的次数很多，将导致越来越多的内存被占用并不被释放。

所有java的内存泄漏问题本质上都是生存周期不一致所造成的引用的游离。

有序表

有序表可以认为是一套规范的接口（抽象类），其底层是的实现机制有：红黑树，AVL数，跳表，SB树。红黑树这个数据结构较为复杂，逐渐被淘汰，现在用SB树实现的多。

有序表和哈希表的区别，有序表中的key是按顺序组织的，因此有序表支持查找最小的key，最大的key，小于等于某个key的数中离key最近的数，大于等于某个key的数中离key最近的数。

有序表的增删改查时间复杂度为O(lonN)O(lonN)

--------------------------------------------------------to be continued--------------------------------------------------------