SF기술인터뷰

이렇지만 는 면접에서 흔히 볼 수 있는 질문인데, 면접 중에도 여전히 많은 학생들이 잘 대답하지 못했습니다. 2의 n승이 답변에 언급되어 있는데, 면접관은 계속해서 관련 질문을 할 가능성이 높습니다. 그래도 여전히 불분명하다면 HashMap을 체계적으로 공부하는 것이 좋습니다. 🎜

이전에 내 블로그에 두 개의 기사를 게시한 적이 있습니다: 🎜 blockquote >

HashMap요소 추가 프로세스

HashMapPut에 요소를 추가하는 과정은 다음 9단계로 나눌 수 있습니다. 🎜

• 1. put() 메소드를 사용할 때 putVal() 메소드
• 2를 직접 호출합니다. 2. Put할 때 먼저 배열이 비어 있는지 확인하고, 비어 있으면 크기 조정 작업을 수행합니다.
• 3 해시로 배열 색인화 길이 -1을 키의 해시 값과 AND하여 배열의 색인을 가져옵니다. 색인으로 지정된 위치가 비어 있으면 삽입할 수 있고 새 노드를 삽입할 수 있음을 의미합니다. 직접
• 4. 현재 키가 존재하는지 확인하고, 교체에 성공하면 이전 값을 반환합니다.
• 5. 트리 유형인 경우 트리 연산에 따라 추가합니다. 새로운 노드 내용
• 6. 해시 충돌이 발생한 노드가 트리 유형이 아닌 경우 현재 충돌이 발생했음을 의미합니다. 그러면 이때 루프 처리 로직이 들어갑니다
• 7. 루프 로직을 입력한 후 먼저 무엇을 처리하고 있는지 확인하고 충돌 노드의 다음 노드가 비어 있는지 확인합니다. 비어 있으면 새 노드를
• 에 넣습니다. 8. 넣은 후 현재 연결 리스트가 최대 허용 연결 리스트 길이인 8을 초과하는지 여부를 판단합니다. 이를 초과하면 삽입을 위해 레드-블랙 트리로 변환됩니다.
• 9. 맵의 인덱스 테이블이 비어 있거나 현재 인덱스 테이블 길이가 64(레드-블랙 트리 변환을 위한 최대 인덱스 배열 테이블 길이)보다 작은 경우 크기 조정 작업을 수행하세요. 충돌된 노드는 비어 있지 않습니다. 그런 다음 노드를 추가하고 충돌된 노드의 트리를 따라 삽입하면 됩니다.

내 블로그에서 블로그 게시물을 읽을 수 있습니다: 3년간의 필수 HashMap 소스 코드: http://www .woaijava.cc/blog/ 211

레드-블랙 트리란 무엇이며 그 특징은 무엇입니까?

Red Black Tree는 특화된 AVL 트리(균형 이진 트리)로 삽입 및 삭제 작업 시 특정 작업을 사용하여 이진 검색 트리의 균형을 유지함으로써 더 높은 검색 성능을 얻습니다.

적흑색 나무에는 5가지 특징이 있습니다.

• 마디는 빨간색 또는 검은색입니다.

• 루트 노드는 검은색입니다.

• 모든 잎은 검은색입니다(잎은 NIL 노드입니다)

• 각 빨간색 노드의 두 하위 노드는 검정색입니다. (각 리프에서 루트까지의 모든 경로에 두 개의 연속된 빨간색 노드가 있을 수 없습니다.)

• 모든 노드에서 각 리프까지의 모든 경로에는 동일한 수의 검정색 노드가 포함됩니다.

사실 이 질문은 어렵지 않습니다. 면접관 중 일부가 좌우로 회전하는 레드-블랙 트리의 작동에 대해 질문할 수도 있다는 점입니다. 저는 수백 명을 인터뷰했는데, 단 한 명뿐이었습니다. 그것을 말할 수 있는 사람은 거의 없습니다.

B+ 트리의 특징, 최대 몇 개의 레이어, 몇 개의 데이터를 저장할 수 있나요?

B+ 트리의 특징은 두 가지입니다:

• 1. 즉, 리프가 아닌 노드는 키만 저장할 수 있지만 값은 저장할 수 없습니다
• 2. 트리의 모든 리프 노드는 순서가 지정된 연결 목록을 형성하며 모든 데이터는 키 정렬 순서로 탐색될 수 있습니다. .

B+ 나무는 보통 1차선 3층으로 되어있습니다.

InnoDB 페이지 크기기본값은 16KB입니다:

• 레코드 크기가 1KB라고 가정하면 데이터 페이지에 16개의 데이터를 저장할 수 있습니다(페이지의 다른 데이터 구조는 무시)
• 기본 키가 int 이고 포인터 크기가 6B라고 가정하면 인덱스 페이지는 16KB/(4B+6B)©1638 인덱스 16KB/(4B+6B)≈1638个索引

所以，两层的B+树可以存储：16*1638=26208条数据；三层的B+树可以存储：16*1638*1638=42928704条数据。

MySQL的索引为什么使用B+树而不使用跳表？

B+树是多叉树结构，每个结点都是一个16k的数据页，能存放较多索引信息，所以扇出很高。三层左右就可以存储2kw

따라서 2계층 B+ 트리는 다음을 저장할 수 있습니다: 16*1638=26208 데이터 조각, 3계층 B+ 트리는 다음을 저장할 수 있습니다: 16*1638*1638=42928704 데이터 조각. 🎜🎜🎜🎜 MySQL의 인덱스는 왜 점프 테이블 대신 B+ 트리를 사용하나요? 🎜🎜🎜🎜🎜B+ tree🎜는 다중 트리 구조입니다. 각 노드는 16k 데이터 페이지로 더 많은 인덱스 정보를 저장할 수 있으므로 팬아웃이 매우 높습니다🎜. 🎜세 개의 레이어🎜를 저장할 수 있습니다.2kw 데이터 약. 즉, 데이터를 한 번 쿼리하는 경우 이러한 데이터 페이지가 모두 디스크에 있는 경우 디스크 IO를 최대 🎜세 번🎜 쿼리해야 합니다. 🎜

Jump list는 연결 리스트 구조로, 데이터 1개는 노드 1개입니다.2kw 데이터이며 각 쿼리는 2kw数据，且每次查询都要能达到二分查找的效果，2kw大概在2的24次方左右，所以，跳表大概高度在24层左右。最坏情况下，这24层数据会分散在不同的数据页里，也即是查一次数据会经历24次磁盘IO。

因此存放同样量级的数据，B+树的高度比跳表的要少，如果放在MySQL数据库上来说，就是磁盘IO次数更少，因此B+树查询更快。

而针对写操作，B+树需要拆分合并索引数据页，跳表则独立插入，并根据随机函数确定层数，没有旋转和维持平衡的开销，因此跳表的写入性能会比B+树要好。

其实，MySQL的存储引擎是可以换的，以前mysql 5.5是myisam，后来才有的innodb，它们底层索引用的都是B+树。也就是说，你完全可以造一个索引为跳表的存储引擎装到MySQL里。事实上，facebook造了个rocksDB的存储引擎，里面就用了跳表。直接说结论，它的写入性能确实是比innodb要好，但读性能确实比innodb要差不少。感兴趣的话，可以在文章最后面的参考资料里看到他们的性能对比数据。

Redis이진 검색, 2kw는 약 2의 24제곱이 대략이므로 점프대의 대략적인 높이는 24층

정도입니다. 최악의 경우 이러한 24개 데이터 계층은 서로 다른 데이터 페이지에 분산됩니다. 즉, 하나의 데이터 쿼리에는

24개의 디스크 IO

가 필요합니다. 🎜🎜그래서 같은 양의 데이터를 저장하려면 B+ 트리의 높이가 스킵 테이블의 높이보다 작습니다. MySQL 데이터베이스에 배치하면 🎜디스크 IO 수가 적으므로 B+ 트리가 됩니다. 쿼리가 더 빠릅니다🎜. 🎜🎜 🎜쓰기 작업🎜의 경우 B+ 트리는 인덱스 데이터 페이지를 분할 및 병합해야 하며 건너뛰기 테이블은 독립적으로 삽입되며 레이어 수는 무작위 함수에 따라 결정됩니다. 회전 및 균형 유지에 대한 오버헤드가 없습니다. , 그래서 🎜스킵 테이블의 쓰기 성능은 B+ 트리보다 낫습니다. 🎜🎜🎜사실 MySQL의 🎜스토리지 엔진은 변경될 수 있습니다🎜. 이전에 mysql 5.5는 myisam, 나중에 나온innodb, 기본 인덱스는 모두 🎜B+ 트리🎜를 사용합니다. 즉, 스킵 테이블 인덱스로 스토리지 엔진을 완벽하게 구축하고 이를 MySQL에 설치할 수 있다. 실제로 facebook이 rocksDB의 스토리지 엔진, 🎜호핑 테이블 🎜을 사용 . 결론부터 말하자면 🎜쓰기 성능🎜은 innodb보다 확실히 낫지만, 🎜읽기 성능🎜은 innodb보다 훨씬 나쁩니다. 관심이 있으시면 기사 마지막 부분에 있는 🎜참고자료🎜에서 성능 비교 데이터를 확인하실 수 있습니다. 🎜

🎜🎜Redis B+ 트리나 이진 트리 대신 건너뛰기 목록을 사용하는 이유는 무엇입니까? 🎜🎜🎜🎜B+ 트리의 원리는 리프 노드가 데이터를 저장하고 리프가 아닌 노드가 인덱스를 저장하기 때문입니다. B+ 트리의 각 노드는 여러 개의 키워드를 저장할 수 있으므로 노드 크기를 디스크 페이지 크기로 최대한 활용할 수 있습니다. 디스크 전처리 기능. 디스크 페이지를 읽을 때마다 전체 노드를 읽습니다. 각 리프 노드에는 디스크 IO를 최소화하기 위해 이전 노드와 다음 노드에 대한 포인터도 있습니다. 메모리에서 데이터를 읽는 데 걸리는 시간은 디스크에서 IO를 읽는 시간의 100만분의 1이고 Redis는 IO를 포함하지 않고 메모리에서 데이터를 작업하므로 건너뛰기 테이블이 사용됩니다.

인덱스 생성 시 주의할 점은 무엇인가요?

이 질문은 어떤 SQL 최적화를 알고 있는지 물을 때도 사용할 수 있습니다.

• 인덱싱에 가장 적합한 열은 WHERE 子句中的列，或连接子句中的列，而不是出现在 SELECT 키워드 뒤에 나타나는 열입니다.
• 인덱스 열의 카디널리티가 클수록 인덱싱 효과가 더 좋습니다.
• 상황에 따라 복합 인덱스를 생성하면 쿼리 효율성을 높일 수 있습니다.
• 인덱스를 너무 많이 생성하지 마세요. 이렇게 하면 추가 디스크 공간을 차지하고 쓰기 작업의 효율성이 떨어집니다.
• 기본 키에 대해 가능한 한 짧은 데이터 유형을 선택하면 인덱스의 디스크 사용량을 효과적으로 줄이고 쿼리 효율성을 높일 수 있습니다.
• 문자열을 색인화할 때 접두사 길이를 맞춤설정해야 색인 공간을 많이 절약할 수 있습니다.

한 테이블의 데이터 양이 수천만 개가 넘는 경우 어떻게 최적화하나요?

1. 데이터베이스를 설계하고 테이블을 생성할 때 성능 문제를 고려하세요. 예를 들어 단일 테이블에 필드가 너무 많으면 안 됩니다. 인덱스가 많을수록 좋습니다. 고려사항 WHERE 및 ORDER BY 명령에 포함된 컬럼을 인덱스할 때 EXPLAIN을 사용하여 인덱스 또는 전체 테이블 스캔을 사용하는지 확인하고 적절한 데이터 유형을 선택하고 적절한 인덱스 유형 등

2. SQL을 작성할 때 주의가 필요합니다. 예를 들어, 목록 데이터에 대해 전체 테이블을 사용하지 마십시오. 페이지 수를 너무 많이 사용하면 느린 SQL을 찾을 수 없습니다. * 느린 쿼리 로그를 켜서 찾을 필드 등을 나열합니다.

3. 스토리지 엔진 선택, MyISAM은 SELECT 집약적인 테이블에 적합하고 InnoDB는 INSERT 및 UPDATE 집약적인 테이블에 적합합니다.

4. 하위 데이터베이스 및 하위 테이블 예: 하위 데이터베이스 데이터베이스를 여러 개로 나누는 것이 좋습니다. 실제로 하위 데이터베이스를 수행하면 많은 개발 비용이 발생합니다. 이득을 얻을 가치가 없습니다! 테이블 분할은 위의 프로세스에 따라 큰 테이블을 최적화하는 것이지만 여전히 쿼리가 중단된 경우 테이블을 여러 테이블로 나누고 하나의 쿼리를 여러 쿼리로 나눈 다음 반환합니다. 사용자에게 결과를 결합합니다. 테이블 분할은 수직 분할과 수평 분할로 구분되며, 분할 항목은 특정 필드를 주로 사용합니다. 예를 들어, id 필드는 테이블을 100개의 테이블로 분할하는 데 사용됩니다. 테이블 이름은 tableName_id%100입니다. 그러나 하위 테이블은 소스 프로그램 코드를 수정해야 하므로 개발에 많은 노력이 필요하고 개발 비용이 크게 증가합니다. 따라서 개발 초기 단계에서 대량의 데이터 존재를 고려하는 경우에만 적합합니다. 하위 테이블 처리 작업이 잘 수행되고 있으며 애플리케이션에 적합하지 않습니다. 온라인 상태가 된 후 수정하려면 비용이 너무 많이 듭니다.

5. 하드웨어 업그레이드, 이 방법이 가장 간단하지만 상대적인 비용도 높아서 사장님이 꺼려하십니다.

6. 데이터베이스 업그레이드 예: MySQL 데이터베이스를 빅데이터 엔진으로 교체하여 데이터를 처리하거나, POLARDB로 교체합니다. POLARDB는 Alibaba Cloud가 개발한 차세대 관계형 분산 클라우드 네이티브 데이터베이스입니다. MySQL과 호환되며 가장 높은 저장 용량을 가지고 있으며 100T에 도달할 수 있으며 성능은 MySQL의 최대 6배입니다.

500만 개의 데이터가 포함된 테이블 a와 300만 개의 데이터가 포함된 테이블 b가 외래 키 tid를 통해 연결됩니다. 50000부터 50200까지 조건에 맞는 200개의 데이터 레코드를 어떻게 빠르게 쿼리할 수 있을까요?

방법 1: 테이블 a의 tid가 자체 증가하고 연속적인 경우 테이블 b의 id가 인덱스입니다. SQL 문은 다음과 같습니다.

select * from a,b where a.tid = b.id and a.tid>500000 limit 200;

로그인 후 복사

방법 2: 테이블 a의 tid가 연속적이지 않은 경우 포함 인덱스를 사용해야 합니다. tid는 기본 키이거나 보조 인덱스이고 테이블 b의 id도 인덱스해야 합니다. SQL 문은 다음과 같습니다.

select * from b, (select tid from a limit 50000,200) a where b.id = a.tid;

로그인 후 복사

JVM의 메모리 모델에 대해 이야기해 보겠습니다

JVM 메모리 구조에는 프로그램 카운터, 힙 메모리, 메서드 영역 및 스택(Java 가상 머신 스택 및 기본 메서드 스택)이 포함됩니다.

프로그램 카운터 레지스터는 작은 메모리 공간으로, 그 기능은 현재 스레드에서 실행되는 바이트코드의 줄 번호 표시기로 간주될 수 있습니다. 가상 머신의 개념적 모델(단지 개념적 모델일 뿐이며 다양한 가상 머신이 보다 효율적인 방식으로 구현될 수 있음)에서 바이트코드 인터프리터는 실행해야 할 다음 단계를 선택하기 위해 이 카운터의 값을 변경하여 작동합니다. 바이트코드 명령, 분기, 루프, 점프, 예외 처리 및 스레드 복구와 같은 작업은 모두 이 카운터를 사용하여 완료됩니다.

힙 메모리는 JVM의 가장 큰 부분으로 Young Generation과 Old Generation으로 구성됩니다. Young Generation 메모리는 Eden 공간, From Survivor 공간, To Survivor 공간의 세 부분으로 구분됩니다. 8:1:1 ;

메소드 영역은 클래스 정보, 상수, 정적 변수 및 기타 데이터를 저장하는 영역입니다. Java 힙과 구별하기 위해 메소드 영역에도 Non라는 별명이 있습니다. -Heap(비힙); 스택은 Java 가상 머신 스택으로 구분되며 로컬 메소드 스택은 주로 메소드 실행에 사용됩니다. 메소드 영역은 명세로 이해될 수 있으며, 그 구현은 영구 생성, 메타 공간 등이다.

Java Virtual Machine Stacks(Java Virtual Machine Stacks)도 스레드 전용입니다. 수명 주기는 스레드의 수명 주기와 동일합니다. 가상 머신 스택은 Java 메소드 실행의 메모리 모델을 설명합니다. 각 메소드가 실행되면 스택 프레임(Stack Frame)이 동시에 생성되어 지역 변수 테이블, 작업 스택, 동적 링크, 메소드 종료 등의 정보를 저장합니다. , 등. 각 메서드가 호출되어 실행이 완료될 때까지의 과정은 가상 머신 스택의 스택 프레임이 스택에서 푸시되어 스택 밖으로 튀어나오는 과정에 해당합니다.

네이티브 메소드 스택과 가상 머신 스택은 매우 유사한 역할을 합니다. 유일한 차이점은 가상 머신 스택이 Java 메소드(즉, 바이트코드)를 실행하는 가상 머신을 제공하는 반면, 네이티브 메소드 스택은 네이티브 메소드를 제공한다는 것입니다. 가상 머신에서 사용됩니다. 가상 머신 사양은 로컬 메소드 스택의 메소드 언어, 사용법, 데이터 구조를 요구하지 않으므로 특정 가상 머신에서 자유롭게 구현할 수 있습니다.

Survivor 영역이 필요한 이유는 무엇인가요?

Survivor가 없으면 Eden 영역에서 Minor GC가 수행될 때마다 연령 제한이 없으며 살아남은 개체가 Old Generation으로 전송됩니다. 결과적으로 Old Generation이 빠르게 채워지면서 Major GC가 발생하게 됩니다. (Major GC에는 보통 Minor GC가 동반되기 때문에 Full GC가 발생하는 것으로 볼 수도 있습니다.) Old 세대의 메모리 공간은 신세대에 비해 훨씬 크고, Full GC는 Minor GC보다 훨씬 오래 걸립니다.

면접관은 다음과 같이 질문할 수 있습니다. 긴 실행 시간의 단점은 무엇입니까?

잦은 전체 GC는 오랜 시간을 소비하며 대규모 프로그램의 실행 및 응답 속도에 영향을 미칩니다.

Old Generation 공간이 늘어나면 더 많은 생존 개체가 Old Generation을 채울 수 있습니다. Full GC 빈도는 감소하지만 Old Generation 공간이 증가함에 따라 Full GC가 발생하면 실행 시간이 길어집니다.

Old Generation 공간이 줄어들면 Full GC에 소요되는 시간은 줄어들지만 곧 Old Generation은 살아남은 개체로 가득 차고 Full GC의 빈도가 높아질 것입니다.

그래서 Survivor의 존재 의미는 Old Generation으로 전송되는 객체를 줄여서 Full GC의 발생을 줄이는 것입니다. Survivor의 사전 스크리닝은 16번의 Minor GC 이후에 새로운 세대에서 살아남을 수 있는 객체만 전송되도록 보장하는 것입니다. 노년.

저한테 물어볼거 있으신가요?

일부 면접관들은 이 질문을 정중하게 묻고 답변에 별로 신경을 쓰지 않습니다. 왜냐하면 이 시기의 면접은 아마도 멋있을 것이기 때문입니다.

그러나 질문할 기회가 있으면 대부분의 사람들은 여전히 ​​당신이 좋다고 생각하고 합격 가능성이 매우 높기 때문에 여전히 신중하게 대답해야 합니다

그 사람의 사고 방식이 어떻든 우리는 단지 잘 행동하기 위해.

이 질문은 불필요한 것처럼 보일 수도 있지만 실제로는 매우 중요합니다. 일반적으로 면접관은 직원의 개성과 혁신 능력에 큰 관심을 갖기 때문에 “문제 없습니다”라고 말하는 사람을 좋아하지 않습니다. 회사는 구직자가 개인 혜택에 대해 질문하는 것을 좋아하지 않습니다. 회사에 신입사원을 위한 교육 프로그램이 있습니까? 아니면 회사의 홍보 메커니즘은 무엇입니까? 회사는 여러분의 배움에 대한 열정과 회사에 대한 충성심, 야망을 보여주기 때문에 여러분을 환영할 것입니다.