补漏

妖狐艹你老母 2022-03-18 06:54 182阅读 0赞

\*\*

## 排序算法： ##

\*\*  
快排(python):

def quick_sort(a,low,high):
        start = low
        end = high
        key = a[low]
    
        while(end > start):#此处控制循环不停的迭代
            # (第一次)从后往前
            while start < end and key <= a[end]:
                end = end -1
            if(key >= a[end]):
                tmp = a[start]
                a[start] = a[end]
                a[end] = tmp
            #(第一次)从前往后
            while start < end and key >= a[start]:
                start = start + 1
            if(a[start] >= key):
                tmp = a[end]
                a[end] = a[start]
                a[start] = tmp
            print('start:'+str(start)+'\t'+'end:'+str(end))
          #此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
        if(start > low):
            quick_sort(a,low,start-1)
        if(end < high):
            quick_sort(a,end+1,high)
        return a

冒泡排序：先从数组中找到最大值(或最小值)并放到数组最左端(或最右端)，然后在剩下的数字中找到次大值(或次小值)  
过程中不重新定义其他参数，只是元素的两两比较

// 冒泡排序
    void BubbleSort(int arr[], int length)
    {
    	for (int i = 0; i < length; i++)
    	{
    		for (int j = 0; j < length -  i - 1; j++)
    		{
    			if (arr[j] > arr[j + 1])
    			{
    				int temp;
    				temp = arr[j + 1];
    				arr[j + 1] = arr[j];
    				arr[j] = temp;
    			}
    		}
    	}
    }

选择排序：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。

// 选择排序
    void SelectionSort(int arr[], int length)
    {
    	for (int i = 0; i < length; i++)
    	{
    		int index = i;
    		for (int j = i+1; j < length; j++)
    		{
    			if (arr[j] < arr[index])
    			{
    				index = j;
    			}
    		}
    		if (index == i)
    			continue;
    		else
    		{
    			int temp;
    			temp = arr[index];
    			arr[index] = arr[i];
    			arr[i] = temp;
    		}
    	}
    }

\*\*

## 查找算法： ##

\*\*  
二分查找(排序的数组必须是有序的)：

def binary_search(a,key):#升序排列
        len_ = len(a)
        if len_ < 1:
            return False
    
        mid =  len_ // 2
        if key < a[mid]:
            return binary_search(a[:mid],key)
        elif key > a[mid]:
            return binary_search(a[mid+1:],key)
        else:
            return True
    
    if __name__ == '__main__':
        lis = [2,4, 5, 12, 14, 23]
        if binary_search(lis, 15):
            print('ok')

\*\*

## Java专栏 ##

\*\*  
HashMap工作原理：  
HashMap(非同步、线程不安全)  
1、允许使用null键和null值  
2、影响HashMap实例的两个参数：初始容量和加载因子  
HashMap的数据结构：数组+链表组成；寻址容易，插入和删除容易  
HashMap事实上是一个线性的数组实现的，所以能够理解为其存储数据的容器是一个线性容器  
HashMap里面有一个内部静态类Entry，其重要的属性有key、value、next;Entry是键值对实现的一个基础bean。也就是说HashMap的基础就是一个线性数组，这个数组就是Entry\[\]，Map里面的内容都保存  
在Entry\[\]中；  
数组的作用是存储链表中第一个节点的地址值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmd5YW5nX3lhbmdxaQ_size_16_color_FFFFFF_t_70]  
当哈希表中条目数超过了当前容量与加载因子的乘积时，哈希表将会作出自我调整，将容量扩充为原来的两倍，并且重新将原有的元素重新映射到表中，  
看不懂？那就再看看下面的  
HashMap存取实现  
存储算法：  
int hash=key.hashcode();  
int index=hash%Entry\[\].length;//获得数组下标：key的hash值对Entry数组长度进行取余  
Entry\[index\]=value;  
注意：假设两个key通过hash%Entry\[\].length得到的index同样，会不会覆盖？  
是不会的。Entry类有一个next属性，作用是指向下一个Entry。打个例如， 第一个键值对A进来。通过计算其key的hash得到的index=0。记做:Entry\[0\] = A。一会后又进来一个键值对B，通过计算其index也等于0，如今怎么办？HashMap会这样做:B.next =A,Entry\[0\] = B,假设又进来C,index也等于0,那么C.next = B,Entry\[0\] = C；这样我们发现index=0的地方事实上存取了A,B,C三个键值对,他们通过next这个属性链接在一起。  
取值算法：  
获取key的hashcode值，通过hash值去计算hash%Entry\[\].length，获取Entry\[hash%Entry\[\].length\],定位到该数组元素之后，再遍历该元素处的链表。  
**再哈希，其目的是为了减少哈希冲突，使元素能够均匀的分布在数组上，从而提高数组的存取效率。**

当返回为 null 时，你不能判断是没有找到指定元素，还是在hashmap 中存着一个value为 null 的元素，因为hashmap允许value为 null.

重点：碰撞探测  
当两个对象的hashcode相同时(他们本身可能并不同)，他们的bucket位置是一样的。因为HashMap使用链表存储对象，这个Entry会存储在链表中。在取值的时候，将会遍历链表找到值对象。怎么着？找到bucket位置之后，调用key.equals()方法会找到链表中正确的节点。

总结:HashMap是基于hashing原理对key-value对进行存储与获取，当使用put()方法添加key-value对时，它会首先检查hashCode的值，并以此获得对应的bucket位置进行存储，当发生冲突时(hashcode值相同的两个不同key)，新的key-value对会以结点的形式添加到链表的末尾。而使用get()方法时，同样地会根据key的hashCode值找到相应的bucket位置，再通过key.equals()方法找到对应的key-value对，最终成功获取value值。

优化：  
使用不可变的、声明作final的对象(比如，String是不可变类，也是final的而且也重写了equals()和hashcode()方法)，并且采用合适的equals()和hashcode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度。

如果HashMap的大小超过了负载因子定义的容量，怎么办？  
在HashMap中，还存在着两个概念：桶(buckets)和加载因子(load factor)  
默认的负载因子大小为0.75，也就是说当一个map填满了75%的bucket时，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这一过程称为rehash。

重新调整HashMap大小存在什么问题？  
在多线程发现HashMap需要重新调整大小时，他们会试着调整大小。在调整大小的过程中，存储在链表中的元素会反过来，因为在移植到新的bucket时，HashMap会将元素放在头部。如果条件竞争了，就会出现死循环。但是多线程为啥要用HashMap？

HashMap、HashTable、ConcurrentHashMap的线程安全问题  
HashMap：线程不安全。HashMap的key和value都可以为null值。key=null的键只能有一个；value=null可以有多个，表示HashMap中没有该键或者表示该键对应的值为null；所以HashMap中应该用containsKey()方法来判断是否有该键。  
HashTable：锁住整张hash表，让线程独占。synchronized是针对整张表的，即每次锁住整张表。安全的背后是巨大的浪费。HashTable的key和value都不可以为null。  
ConcurrentHashMap：一个更快的HashMap，它提供了好得多的并发性。ConcurrentHashMap锁的方式是细粒度的。ConcurrentHashMap将hash表分为16个桶，get、put、remove等操作只需要锁需要用到的桶。  
Map m = Collections.synchronizedMap(new HashMap(…));

**Java StringBuilder StringBuffer String**  
运行速度：StringBuilder > StringBuffer > String  
String最慢的原因：String是字符串常量，StringBuilder和StringBuffer是字符串变量；String创建后是不可以变的，而StringBuilder和StringBuffer是可以变的。  
在线程安全上，StringBuilder是线程不安全的，而StringBuffer是线程安全的。  
最终总结：  
String：适合少量的字符串操作  
StringBuilder：适合单线程下在字符缓冲区进行大量操作的情况  
StringBuffer：适合多线程下在字符缓冲区进行大量操作的情况  
StringBuilder和StringBuffer，字符串都是存放在char\[\]中的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmd5YW5nX3lhbmdxaQ_size_16_color_FFFFFF_t_70]: /images/20220318/24a0e32575954252b5255ea7ed8f951c.png