# byte-dance

**Repository Path**: wzk9261/byte-dance

## Basic Information

- **Project Name**: byte-dance
- **Description**: 数据结构和算法基础
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2019-12-11
- **Last Updated**: 2022-11-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Java 基础

本项目用于复习 Java 基础，包括集合、链表、多线程、JVM 等

## hashCode() & equals()

### 重写 hashCode() 和 equals() 方法

创建一个 Student 类，其中有 id 和 name 两个字段，并写好其 Getter 和 Setter。

使用 IntellJ IDEA 的快捷键 Alt + Insert 自动生成 hashCode() 和 equals() 方法：

```java
@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Student student = (Student) o;
    return Objects.equals(id, student.id) &&
        Objects.equals(name, student.name);
}
```

重写的 equals 方法首先使用 == 符号判断传入对象和当前对象是否相同，若相同直接返回 true；若不相同，则判断传入对象和当前对象是否为一类型，若不相等，直接返回true，若为同一类型，则将传入对象强转为当前对象的类型，判断字段是否都相等。

```java
@Override
public int hashCode() {
    return Objects.hash(id, name);
}
```

继续查看  Object 的 hash 方法：

```java
public static int hash(Object... values) {
    return Arrays.hashCode(values);
}
```

发现其使用到了 Arrays 类的 hashCode 方法：

```java
public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}
```

[科普：为什么 string hashCode 方法选择数字31作为乘子](https://segmentfault.com/a/1190000010799123)

经过上面的工作，被重写了 hashCode() 和 equals() 方法的 Student 类如下：

```java
public class Student {

    private Integer id;

    private string name;

    public Student(Integer id, string name) {
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public string getName() {
        return name;
    }

    public void setName(string name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id) &&
                Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}
```

### HashSet 中加入相同元素

HashSet 不能添加重复的元素，当调用 add(Object) 方法时候，首先会调用 Object 的 hashCode 方法判hashCode 是否已经存在，如不存在则直接插入元素；如果已存在则调用 Object 对象的 equals 方法判断是否返回 true， 如果为 true 则说明元素已经存在，如为 false 则插入元素。

阅读一下 HashSet 的 add(Object) 方法：

```java
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
```

其中成员变量 map 被关键字 transient 修饰：

```java
private transient HashMap<E,Object> map;
```

[Java transient关键字使用小记](https://segmentfault.com/a/1190000010799123)

常量 PRESENT 为一个常量对象，主要用于`map.put(e, PRESENT)==null`判断 map 的某个 key 中之前是否已经存值：

```java
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
```

如果`map.put(e, PRESENT)==null`的值为 true，则说明该 key 没有对应的 value，此时`add(E e)`的返回值也为 true，说明可以将该值存入 HashSet 中。

同时由 add 方法我们也可以看出，HashSet 中存放元素使用的是 HashMap，而且是将值存到 HashMap 的 key 中，这一点可以从 HashSet 的其他方法中看出：

1. 获取大小

   ```java
   public int size() {
       return map.size();
   }
   ```

2. 移除元素

   ```java
   public boolean remove(Object o) {
       return map.remove(o)==PRESENT;
   }
   ```

3. 清除所有元素

   ```java
   public void clear() {
       map.clear();
   }
   ```

4. 是否为空

   ```java
   public boolean isEmpty() {
       return map.isEmpty();
   }
   ```

5. 迭代器

   ```java
   public Iterator<E> iterator() {
       return map.keySet().iterator();
   }
   ```

作为对比，ArrayList 则是把元素放在数组中：

```java
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
```

同样是一个被 transient 修饰的成员变量数组：

```java
transient Object[] elementData; // non-private to simplify nested class access
```

由 HashSet 和 ArrayList 的特性，可以写出以下 demo 类用于测试 Student：

```java
public class EqualsDemo {

    public static void main(string[] args) {
        List<Student> studentList = new ArrayList<>();
        // 利用 HashSet 不能加入重复元素的特性
        Set<Object> studentSet = new HashSet<>();

        Student student1 = new Student(1, "张三");
        Student student2 = new Student(1, "张三");

        System.out.println("student == student2: " + (student1 == student2));
        System.out.println("student1.equals(student2): " + student1.equals(student2));
        System.out.println("student1 hashCode: " + student1.hashCode());
        System.out.println("student2 hashCode: " + student2.hashCode());

        studentList.add(student1);
        studentList.add(student2);
        System.out.println("list size: " + studentList.size());

        studentSet.add(student1);
        studentSet.add(student2);
        System.out.println("set size: " + studentSet.size());

        student1.setName("李四"); // 可以尝试把 student1 改为 student2
        boolean removingStudent1 = studentSet.remove(student1);
        System.out.println("after removing student1, removing result: " + removingStudent1 +
                ", set size: " + studentSet.size());

        boolean removingStudent2 = studentSet.remove(student2);
        System.out.println("after removing student2, removing result: " + removingStudent2 +
                ", set size: " + studentSet.size());

    }

}
```

最终输出结果如下：

```shell
student == student2: false
student1.equals(student2): true
student1 hashCode: 775881
student2 hashCode: 775881
list size: 2
set size: 1
after removing student1, removing result: false, set size: 1
after removing student2, removing result: false, set size: 1
```

当某个对象被存到 Set 中时，如果该对象的属性参与了 hashCode 的计算，那么以后就不能修改该对象参与 hashcode 计算的那些属性了，否则会引起意向不到的错误的。正如测试中，不能够移除 student1 对象。

## String

### 直接赋值和 new String 的区别？

- `String str1 = "ABC"`可能创建一个对象或者不创建对象，如果 "ABC" 这个字符串在 String pool 里不存在，会在 String pool创建一个 String 对象 "ABC"。如果已经存在，str1 直接引用这个String pool 里的对象。

- `String str2 = new String("ABC") `至少创建一个对象，也可能两个。因为用到 new 关键字，会在堆中创建一个 str2 的 String 对象，它的 value 是 "ABC"。同时，如果 "ABC" 这个字符串在 String pool 里不存在，会在 String pool 中创建一个 String 对象 "ABC"；如果存在则不创建。

- 关于 String 拼接的单元测试

  ```java
  package string;
  
  import static org.junit.Assert.*;
  import org.junit.Test;
  
  public class StringTest {
  
      @Test
      public void testSimple() {
          String newStr = new String("hello");
          String str = "hello";
          assertEquals(newStr, str);
          assertNotSame(newStr, str);
      }
  
      @Test
      public void testConcat() {
          String whole = "hello world";
          String prefix = "hello";
          final String suffix = " world";
          assertEquals(whole, prefix + suffix);
          assertNotSame(whole, prefix + suffix);
      }
  
      @Test
      public void testConcatFinal() {
          String whole = "hello world";
          final String prefix = "hello";
          final String suffix = " world";
          assertEquals(whole, prefix + suffix);
          assertSame(whole, prefix + suffix);
      }
  
      @Test
      public void testConcatFinalNew() {
          String whole = "hello world";
          final String prefix = new String("hello");
          final String suffix = " world";
          assertEquals(whole, prefix + suffix);
          assertNotSame(whole, prefix + suffix);
      }
  
  }
  ```

  以上四组单元测试均已通过。

### intern 方法

- String 有一个intern() 方法，被 native 关键字修饰，用来检测 String pool 是否已经有这个 String 存在。

### String pool

在 JVM 中存放着一个字符串池，其中保存着很多 String 对象，这些对象可以被共享使用。当以字符串直接创建 String 对象时，会首先在字符串池中查找是否存在该常量。如果不存在，则在 String Pool 中创建一个，然后将其地址返回。如果在 String Pool 中查询到已经存在该常量，则不创建对象，直接返回这个对象地址。

### 为什么说 String 是不可变的？

- String 类用 final 关键字修饰，不能被继承、修改。

  ```java
  public final class String implements java.io.Serializable, Comparable<String>, CharSequence 
  ```

- 成员变量均为 private final，比如：

  ```java
  /** The value is used for character storage. */
  private final char value[];
  
  /** Cache the hash code for the string */
  private int hash; // Default to 0
  ```

  同时，对于私有成员变量，不提供 getter setter

- 为什么 String 被设计为不可变（Immutable）类？

  - HashMap 的 key 不被篡改

    HashMap 经常会使用 String 作为 key，如果 key 是可变的，那么其对应的 value 很有可能就找不到了。

  - String Pool 不被篡改

    因为 String Pool 对 String 的性能优化极为关键，而为了防止 String Pool 中的字符串对象被随意修改，所以设计为不可变。

  - hashCode 可以缓存

    这也是 HashMap 底层的需求，String 是不可变的，那么其对应的 hashCode 也是不变的，可以被缓存，不用每次都计算 hashCode。

  - 线程安全

    String 的 substring 方法如下：

    ```java
    public String substring(int beginIndex, int endIndex) {
        if (beginIndex < 0) {
            throw new StringIndexOutOfBoundsException(beginIndex);
        }
        if (endIndex > value.length) {
            throw new StringIndexOutOfBoundsException(endIndex);
        }
        int subLen = endIndex - beginIndex;
        if (subLen < 0) {
            throw new StringIndexOutOfBoundsException(subLen);
        }
        return ((beginIndex == 0) && (endIndex == value.length)) ? this
            : new String(value, beginIndex, subLen);
    }
    ```

    如果 String 是可变的，即修改 String 的内容后，地址不变。那么当多个线程同时修改的时候，value 的 length 是不确定的，造成不安全因素，无法得到正确的截取结果。而为了保证顺序正确，需要加`synchronzied`，但这会得到难以想象的性能问题。