基础篇-类+结构+Map+二分法+装饰器模式

你有种再说一遍

基础篇-类+结构+Map+二分法
不少人看李小科的视频被带坏了,总是写static函数,殊不知不写static可以减少类内部方法的传参.
为了纠正大家,所以写了本帖子.

# 类
0x01 刚开始为了追求简单,
把所有的字段都写成了定义,而不是声明:
class Info {
  public string A = GetName("name");
  public float B = 1.2f;
}

// 遍历输出,发现已经有值,证明初始化赋值是占用时间的.
var ls = new Info[5];
for (int j = 0; j < ls.Length; j++) {
    Console.WriteLine($"ls[{j}].A = {ls[j].A}");
}

0x02 后来为了反序列化时候可以不被初始化赋值,毕竟反序列化也是必然从配置读取赋值到字段,会覆盖掉初始化.因此写成声明形式:
class Info {
  public string A;
  public float B;
  public Info(){}
  public Info(string a,float b){A=a;B=b;}
}

0x03 再后来发现几点:
a,为了序列化使用缺省构造对象,用来在数组容器长度占位置的,不要初始化赋值.
b,构造函数是不能耗时,应该直接参数映射.
c,构造函数抛异常是很诡异的,会引起定位困难.
构造函数校验参数抛出异常通常发生在编码阶段会被发现,但并不是一个优秀的方法.
如果像0x01直接赋值字段,字段赋值会在构造函数之前完成(且runtime保证线程安全),那么假设中途发生异常之后,字段是需要析构的,类析构行为又会被传递上去字段的析构.那么debug的调用栈上面充满了信息.
析构函数也同样不能抛异常.
构造函数是统一处理赋值,而不是用来校验参数,要保证它的纯洁性.
为此,采取静态方法校验参数和返回构造,从源头防止构造错误又析构的行为.
d,创建时求参数的逻辑大概率是通用的,可以集成到类中,用静态函数实现.外部调用时,可以更简洁地创建对象.
e,私有构造函数,常见于封装,再提供静态构造去实现逻辑.

class Info {
  public string A;
  public float B;
  public Info(){}
  // 私有构造
  private Info(string a,float b){A=a;B=b;}
  // 静态方法返回构造
  public static Info Create(int a,int b) {
     return new Info(a.ToString(), a+b);
  }
  // 隐式转换,通常是类转类
  public static implicit operator Info(Info2 v) {
     return new Info(v.GetName(), v.GetAge());
  }
}

# 结构
0x04 后来为了性能提升,发现经常有List<Info>的操作,CPU预读内存是读取整个类,如果只是使用一个字段,那么仍然会跳跃一个类大小,所以是内存不友好,那么就需要写成SOA结构:
struct Info {
  public List<string> A;
  public List<float> B;
}
细心的观众发现我换了结构体struct,为什么呢?
"new"这个东西,
在c++的意思是:在堆创建,并且全部设置成0.
而c#则是,如果是struct就栈分配,class就堆分配.

如果是栈上面分配岂不是不能返回?但是用过的人都知道是可以返回的呀.
答案:返回值优化(RVO)和拷贝消除,这种编译器技术可以不深入.

0x05 记录类型
public record Info(string a, int b);
一旦创建它是只读的,无法修改,它是值类型,而且默认实现了GetHashcode,更方便啦.
为什么存在这样的结构?因为有序结构是不能更改的,一旦更改岂不是无序了.

# 重温说明
值类型(结构体):
存储在栈上,而不是托管堆上.
被赋值或作为参数传递时,整个值会被复制.
不会引发垃圾回收.
避免装箱拆箱.
高效的键比较:结构体的值可以直接用于比较,而不需要通过对象引用进行间接比较(引用指针跳跃,开辟栈帧).
快速哈希计算:结构体的哈希值可以直接计算,而不需要额外的内存分配或引用处理.

引用类型(类):
存储在托管堆上,而引用存储在栈上.
被赋值或作为参数传递时,仅复制引用,而不复制对象本身.
会引发垃圾回收.

类的属性
看到这里有人会觉得为什么用字段而不用属性?
有时候当然用属性了,但是属性不是必须要用.
属性本质是函数包裹进行访问的过程,它在访问时候会开辟栈帧.
你没有访问行为控制用个鸡儿属性.
你没有注入行为用个鸡儿属性.
你高性能场景用个鸡儿属性.
不会有人因为编辑器提示而去加属性吧.
因为存在动态注入,所以开启Release也不会消除空实现的属性.

# 栈上面分配数组
```c#
public void test() {
    unsafe {
        int size = 1024;
        int* buffer = stackalloc int[size];
        for (int j = 0; j < size; j++) { buffer[j]=j; }
    }
}
```
stackalloc这是c#7.0支持的,在此之前,由于语言本身不直接支持在栈上分配数组,开发者通常使用以下方法来处理需要在栈上分配内存的场景:
1使用本地变量,2使用结构体.

# 动态类型Map
有没有想过,结构和map其实是一回事呢?
你想想class.A和struct.A和map("A")它们不就是一个占用空间和寻址的区别而已嘛?
那么寻址足够快,是不是相当于动态的结构体了,这就是为什么java1.8要优化这个Hashmap,采用位运算指令周期少,而取余的周期高(它跑的是除法器http://bbs.mjtd.com/thread-190705-1-1.html).

## 线程不安全版本:无序Map
1,用除法器取余求hash槽位置
C#的Dictionary
C++的std::unordered_map
2,无除法器
JDK1.8的HashMap,内部用了2次方容量,按位运算求槽位置,并且槽会自动从链表扩容为红黑树.

## 线程不安全:有序Map
1,树排序Map
C#的实现是AVL树:SortedDictionary
C++是红黑树:std::map
2,插入序Map
JS的Map,本质就是一个链表+HashMap.
Add的时候一起加入链表,这样迭代器就可以用链表,就是一个有插入序的容器.其实链表换成动态数组更好,因为如果为了迭代,那么加入SIMD可以更快速查询.
C#实现:
https://gitee.com/inspirefunctio ... al/LinkedHashMap.cs

## 线程安全:并发有序Map
你会发现并发有序容器怎么C#不提供?
Mysql的B+树/PG的LSM树:针对磁盘优化.
Redis的/Java的:内存友好,减少锁.
这些数据库的基础结构,本质也是一个并发有序的KV结构,都是针对性优化的产品.

无锁跳表(其实就是CAS锁)
Rust版本:
https://zhuanlan.zhihu.com/p/600729377
Java版本:
https://segmentfault.com/a/1190000044039605
跳表无锁并发的秘密(视频): https://v.douyin.com/iBJwRvjS

## 线程安全:并发无序Map
C#的ConcurrentDictionary.
它的key是支持int.缺少并发有序容器,是不是可以用它代替呢?
答案是不行,毕竟树才能排序,否则扩容机制就会在hash冲突转为链表.
C#没有实现无锁跳表,需要参考Java自行实现,好在现在Java视频满天飞,以及Github很多写好的.

Java的ConcurrentHashMap.
它的hashcode是类头自带的,虽然也可以类重写.
跳表和红黑树时间比较(视频): https://v.douyin.com/iBJcVVoa

## 平衡度好的C++Map
韦易笑 https://zhuanlan.zhihu.com/p/31758048

## 最快的Map
当然是预估数据之后的开放寻址法的Map了,在十亿行天文台数据挑战:
https://segmentfault.com/a/1190000044679461

## 弱引用WeakMap
JS的WeakMap,是"弱引用键,强引用值",它的键一旦回收,值也自动被回收.通常用于瀑布流等图片展示的结构中.
C#自行封装一个使用:
Dictionary<WeakReference<Key>,V Value>.
C++是std::weak_ptr来处理菱形引用.

## JDK1.8的hashmap
0x01
取模就是整数除法器,为了除法器太慢的问题,map内数组长度必须用2次方,然后索引用了按位与代替取模:
hash&(array.length-1)等价hash%array.length(非二次方也行)

0x02
强行把用户预设长度改为2次方长度,所以有了计算邻近数值,capacity容量(数组长度)
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0)? 1 : (n >= maximum_capacity)? maximum_capacity : n + 1;
}
0x03
hashmap扩容和缩容时候,考虑负载因子0.75(泊松分布概率),红黑树阶数.
哈希冲突时候,利用链表+红黑树,减少上层数组的扩容再散列,给我的感觉就是重复占用的格子面积来决定扩容和缩容.
Rehash扩容算法,遍历每个元素,当 e.hash & oldCap = 0,则节点在新数组中的索引值与旧索引值相同.当 e.hash & oldCap = 1,则节点在新数组中的索引值为旧索引值+旧数组容量.为什么不重新GetHashCode呢?因为计算字符串hash算法慢,需要处理负数hash,高位和低位异或等等.
所以你会发现,为了除法器这碗醋,所以Java包了一顿饺子.

# 二分法
二分法通常用于结构类型太长但是有序的情况,例如ABCDE...这样排序下去page页(储存在磁盘的)
详情参考ES数据库构成:
【Elastic Search是什么？Lucene是什么？架构是怎么样的？-哔哩哔哩】 https://b23.tv/e5HKWmm

1.确保你的List<T>是有序的;如果不是,先对其进行排序;
2.调用BinarySearch方法,并传入要搜索的值;
3.BinarySearch方法会返回一个整数,表示搜索值在列表中的索引,如果未找到则返回一个负数;
4,找到的索引后面也可能是同一个值,需要索引++获取.

```csharp
using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        // 无序的数据源
        List<int> numbers = new List<int> { 1, 3, 5, 7, 9, 11, 13, 7, 7, 15, 17, 19 };
        // 排序,不创建新数组
        numbers.Sort();
        // 排序,会返回新数组
        // numbers = numbers.OrderBy(x=>x).ToList();
        // 要搜索的值
        int searchValue = 7;
        int index = numbers.BinarySearch(searchValue);

        if (index < 0) {
          Console.WriteLine("未找到");
          return;            
        }
        Console.WriteLine($"索引为:{index}");
    }
}
```

如果你的列表中的数据类型是自定义的,并且你想根据某个特定的属性进行搜索,
那么你可以使用BinarySearch的重载版本,传入一个自定义的比较器IComparer<T>;

```csharp
using System;
using System.Collections.Generic;

class Person {
    public string Name { get; set; }
    public int Age { get; set; }
    public Person(string name, int age)  {
        Name = name;
        Age = age;
    }
}

class Program {
    static void Main() {
        List<Person> people = new List<Person>
        {
            new Person("Alice", 25),
            new Person("Bob", 30),
            new Person("Charlie", 35),
            // ... 更多人员
        };
        // 根据年龄排序
        people.Sort((a, b) => a.Age.CompareTo(b.Age));
        //要搜索的年龄
        int searchAge = 30;
        int index = people.BinarySearch(new Person("", searchAge), (a, b) => a.Age.CompareTo(b.Age));

        if (index < 0) {
         Console.WriteLine($"未找到年龄为 {searchAge} 的人;");
       return;
        }
       Console.WriteLine($"找到了年龄为 {searchAge} 的人在索引 {index} 处;");
    }
}
```

# 装饰器模式
以前我总是想,为什么存在这样奇怪的模式,都写在同一个类上面写完就好了呀.
后来遇到了序列化,发现数据类要纯粹,不能耦合多种方法,不然肉眼比较字段存在困难,以至于出现能省则省的写法.
那么方法提供在哪里呢?这要说到,曲线为什么没有Length属性?
很多人都这样想过,如果有就方便多了,为什么桌子就是不这样提供呢?
想必很多人都是直接写扩展方法来处理不同的图元...这样做虽然没错,只是设计模式用起来就知道爽了.
其实桌子是暴露最底层,上层的话会用一个装饰类提供方法,在装饰类上面通过if/switch/map来处理不同图元,然后暴露一个Length属性.
这样它们就能ent.Length了!!!
这样封装的好处是什么?把底层暴露,把好用的东西藏起来!!!
伪代码示意:
```
var cu = new Curve();
var ent = new 装饰类(cu);
ent.Length
```
(完)

moranyuyan

我看不懂的就是厉害的东东。

414249149

看着很厉害，

qq1254582201

写的很不懂的样子，有精力了好好拜读