神策数据电话面试

发表于 | 分类于 | | 阅读次数:

Stay Hungry, Stay Foolish.

HashMap 底层原理

HashMap是以键值对（key-value）的形式存储元素的。HashMap需要一个hash函数，它使用hashCode()和equals()方法向集合中添加元素或从集合中检索元素。

当调用put()方法的时候，HashMap会计算key的hash值，然后把键值对存储在集合中合适的索引上。如果key已经存在了，value会被更新成新值。

HashMap 如何解决哈希冲突

使用拉链法。

HashMap中哈希表的每一个元素其实是一个链表。当发生哈希冲突时，首先从该哈希索引对应的链表中查找是否已有相同key，若有则更新value即可，否则将使用链表的头插法，将冲突的新键值对插在链表的头部。

HashMap 和 Hashtable 的区别

两者都实现了Map接口，因此很多特性非常相似。但是，他们有以下不同点：

  • HashMap允许键和值是null，而Hashtable不允许键或者值是null。
  • HashMap随着时间的推移，无法保证元素次序是不变的。
  • HashMap提供了fail-fast迭代器，即多线程环境下迭代可能会发生 ConcurrentModificationException。
  • Hashtable是线程安全的，而HashMap不是。
  • Hashtable提供了对键的枚举（Enumeration）。

一般认为Hashtable是一个遗留的类。

Hashtable 如何保证线程安全

因为其每个可能引发线程安全的方法均被synchronized关键字修饰（加上了同步锁）。

HashMap 如何变得线程安全

HashMap<Object, Object> hashMap = new HashMap<>();
Map<Object, Object> map = Collections.synchronizedMap(hashMap);

HashMap 和 LinkedHashMap 的区别

LinkedHashMap 继承自 HashMap，因此具有和其一样的快速查找的特性。

除此之外，LinkedHashMap 额外维护了一个双向链表，用来维护 Map 元素的插入顺序或者LRU（最近最久未使用）顺序。

数组和链表的区别

  • 数组大小固定，链表则可以动态变化。
  • 数组支持快速随机访问，链表只能通过遍历查找元素。
  • 数组插入和删除元素时，涉及到大量元素的移动操作，性能差；而链表在找到插入位置或删除目标后，只需涉及到指针指向的变化，性能好。

手写算法题

题目一：基本字符串压缩

利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。

public class Solution {
    public String zipString(String iniString) {
        StringBuilder sb = new StringBuilder();

        char ch;
        int low = 0, high, count;
        int len = iniString.length();

        while (low < len) {
            high = low;
            ch = iniString.charAt(low);
            while ((high < len) && (iniString.charAt(high) == ch)) {
                high++;
            }
            count = high - low;
            sb.append(ch);
            sb.append(count);
            low = high;
        }

        return (sb.toString().length() < len) ? sb.toString() : iniString;
    }
}

题目二：实现简单哈希表以及查找功能

public class HashTable {
    private List[] base = new List[16];

    public HashTable() {
        for (int i = 0; i < base.length; i++) {
            base[i] = new ArrayList<String>();
        }
    }

    private int hash(String elem) {
        if (elem == null) return -1;
        return elem.hashCode() % 16;
    }

    public void add(String str) {
        int hash = hash(str);
        if (hash == -1) {
            throw new RuntimeException("Can't add null!");
        }
        base[hash].add(str);
    }

    public boolean find(String str) {
        if (str == null) return false;
        int hash = hash(str);
        List<String> temp = base[hash];
        for (String s : temp) {
            if (s.equals(str)) return true;
        }
        return false;
    }
}

10亿整数，1G内存，快速去重

参考博文：https://blog.csdn.net/hustwht/article/details/52181643

什么是虚拟内存（操作系统）

让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。

虚拟内存的最大容量由什么决定

由计算机的地址结构决定，即 CPU 的位数。64位系统环境下，虚拟内存技术使得进程可用内存空间达2的64次幂字节，显然这只是理论数值。

进程和线程的区别

进程是执行着的应用程序，而线程是进程内部的一个执行序列。一个进程可以有多个线程。线程又叫做轻量级进程。

  • 地址空间和其它资源：进程间相互独立，同一进程的各线程间共享。某进程内的线程在其它进程不可见。

  • 通信：进程间通信（IPC技术），线程间可以直接读写进程数据段（如全局变量）来进行通信——需要进程同步和互斥手段的辅助，以保证数据的一致性。

  • 调度和切换：线程上下文切换比进程上下文切换要快得多。

  • 在多线程操作系统中，进程不是一个可执行的实体。

网络 ARP 协议的作用

ARP 是地址解析协议，解决 IP 地址到硬件 MAC 地址的映射问题。

说几个熟悉的 HTTP 状态码

2xx 成功

  • 200 OK：一切正常

3xx 重定向

  • 301 Moved Permanently：客户请求的文档在其他地方

4xx 客户机中出现的错误

  • 400 Bad Request：请求出现语法错误
  • 401 Unauthorized：客户视图未经授权访问受密码保护的页面
  • 403 Forbiden：资源不可用。请求被拒绝
  • 404 Not Found：无法找到指定位置的资源

5xx 服务器中出现的错误

  • 500 Inernal Server Error：服务器遇到意料不到的情况，不能完成客户请求
  • 501 Not Implemented：服务器不支持实现请求所需要的功能
  • 502 Bad Gateway：服务器作为网关或代理，为了完成请求访问下一个服务器，该服务器返回了非法的应答
  • 503 Service Unavailable：服务器由于维护或负载过重未能应答
  • 504 Gateway Timeout：服务器作为网关或代理，不能及时从远程服务器获得应答
  • 505 HTTP Version Not Supported：服务器不支持请求中所指明的 HTTP 版本（HTTP 1.1新）

Linux 查看进程端口

# 先查找进程的 PID
ps -ef | grep thread_name

# 查看进程端口
netstat -anp | grep PID

Linux kill -9 和 kill -15 的区别

kill的参数其实是信号编号。

SIGKILL(9)：立即杀死进程。该信号不能被阻塞，处理和忽略。不推荐~

SIGTERM(15)：正常退出进程，退出前可以被阻塞或回调处理。并且它是 Linux 缺省的程序中断信号。推荐使用！

# 查看全部的信号编号
kill -l
手滑了就鼓励一下吧~