HashMap解析

发表于 2021-08-08 | 分类于 Map

几个核心的成员变量

1	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

初始化桶的大小，因为底层为数组，所以这是数组的默认大小为16

1	static final int MAXIMUM_CAPACITY = 1 << 30;

桶的最大值为$2^{30}$

1	static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认的负载因子为0.75

1	transient int size;

Map中key-value的个数

1	int threshold;

扩容的临界值，当实际K-V个数超过threshold时，HashMap会将数组长度扩容，threshold=capacity*loadFactor

1	final float loadFactor;

负载因子

阅读全文 »

锁的状态和锁的升级过程

发表于 2021-08-07 | 分类于多线程

在synchronized最初的实现方式是“阻塞或唤醒一个Java线程需要操作系统切换CPU状态来完成，这种状态切换需要耗费处理器时间，如果同步代码块中内容过于简单，这种切换的时间可能比用户代码执行的时间还长”，这种方式就是synchronized实现同步最初的方式。

在JDK1.6中为了减少获得锁和释放锁带来的性能消耗，引入了“偏向锁”和“轻量级锁”。

阅读全文 »

排序算法全解析

发表于 2021-08-03 | 分类于 LeetCode

时间复杂度$O(n^2)$级排序算法

冒泡排序

冒泡排序是入门级的算法。通常来说，冒泡排序有三种写法：

一边比较一边向后两两交换，将最大值/最小值冒泡到最后一位；
经过优化写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生过交换表示已经有序，不需要再继续排序；
进一步优化的写法：除了使用一个变量记录当前轮次是否发生过交换，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。

阅读全文 »

数据库系统原理

发表于 2021-08-01 | 分类于 MySQL基础

关系型数据库

关系型数据库是一种建立在关系模型的基础上的数据库。关系模型表明了数据库中所存储的数据之间的联系(一对一，一对多，多对多)。

在关系型数据库中，我们的数据的都被存放在了各种表中，表中的每一行就存放着一条数据。

大部分关系型数据库都使用SQL来操作数据库。并且，大部分关系型数据库都支持事务的四大特性(ACID)。

阅读全文 »

UDP协议解析

发表于 2021-07-28 | 分类于 Computer Networking

UDP的概述

UDP(User Datagram Protocol, 用户数据报协议)。UDP是传输层的协议，功能即为在IP数据报服务之上增加了最基本的服务：复用和分用以及差错检测。

UDP提供不可靠服务，具有TCP所没有的优势：

阅读全文 »

多线程

发表于 2021-07-26 | 分类于多线程

创建和运行线程

Thread类

继承Thread类，重写run方法，或者使用匿名内部类。

@Test
public void threadTest(){
    Thread thread = new Thread(){
        @Override
        public void run(){
            System.out.println("Thread Create");
        }
    };
    thread.setName("t1");
    thread.start();
    System.out.println("Running");
}

可以通过setName给线程设置名字

阅读全文 »

Redis入门

发表于 2021-07-26 | 分类于 Redis

NoSQL数据库简介

web1.0时代，数据访问量很有限，当一夫当关的高性能的单点服务器可以解决大部分问题。

web2.0时代的到来，用户访问量大幅度提升，同时产生了大量的用户数据。加上后来的智能移动设备的普及，所有的互联网平台都面临着巨大的性能挑战。(服务器CPU和内存的压力，数据库服务的IO压力)

阅读全文 »

华为机试题解

发表于 2021-07-24 | 分类于 LeetCode

华为机试练习

阅读全文 »

队列&栈(Queue&Stack)

发表于 2021-07-20 | 分类于 LeetCode

队列：先入先出的数据结构

在FIFO数据结构中，将首先处理添加到队列中的第一个元素。

队列的实现

为了实现队列，我们可以使用动态数组和指向队列头部的索引。队列应支持两种操作：入队和出队。入队向队列追加一个元素，而出队会删除第一个元素。

class MyQueue{
    private List<Integer> data;
    private int pStart;
    public MyQueue(){
        data = new ArrayList<Integer>();
        pStart = 0;
    }
    public boolean enQueue(int x){
        data.add(x);
        return true;
    }
    public boolean deQueue(){
        if(isEmpty() == true){
            return false;
        }
        pStart++;
        return true;
    }
    public int front(){
        return data.get(pStart);
    }
    public boolean isEmpty(){
        return pStart >= data.size();
    }
}

上述实现的缺点：随着起始指针的移动，浪费了越来越多的空间，当我们有空间限制时，这将是难以接受的。

阅读全文 »

链表LinkedList

发表于 2021-07-19 | 分类于 LeetCode

设计链表

class MyLinkedList {

    /** Initialize your data structure here. */
    private int size;
    private Node head;
    private Node tail;

    class Node{
        private int val;
        private Node next;
        private Node prev;
        public Node(int val){
            this.val = val;
        }
    }
    public MyLinkedList() {
        this.size = 0;
        this.head = new Node(-1);
        this.tail = new Node(-1);
        head.next = tail;
        tail.prev = head;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if(index < 0 || index > size - 1){
            return -1;
        }
        Node temp;
        if(index < (size >> 1)){
            temp = head;
            for(int i = 0; i < index + 1; i++){
                temp = temp.next;
            }
        }else{
            temp = tail;
            for(int i = 0; i < size - index; i++){
                temp = temp.prev;
            }
        }

        return temp.val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if(index < 0 || index > size){
            return;
        }
        Node pre, after;
        if(index < (size >> 1)){
            pre = head;
            for(int i = 0; i < index; i++){
                pre = pre.next;
            }
            after = pre.next;
        }else{
            after = tail;
            for(int i = 0; i < size - index; i++){
                after = after.prev;
            }
            pre = after.prev;
        }

        Node newNode = new Node(val);
        newNode.next = after;
        after.prev = newNode;
        pre.next = newNode;
        newNode.prev = pre;
        size++;
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if(index < 0 || index > size - 1){
            return;
        }
        Node pre, after;
        if(index < (size >> 1)){
            pre = head;
            for(int i = 0; i < index; i++){
                pre = pre.next;
            }
            after = pre.next.next;
        }else{
            after = tail;
            for(int i = 0; i < size - index - 1; i++){
                after = after.prev;
            }
            pre = after.prev.prev;
        }

        pre.next = after;
        after.prev = pre;
        size--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

阅读全文 »