散列表练习

1.89 名选手参加学校运动会。为了方便记录成绩，每个选手胸前都会贴上自己的参赛号码。这 89 名选手的编号依次是 1 到 89。现在我们希望编程实现这样一个功能，通过编号快速找到对应的选手信息。

将编号当做数组下标，数组存储选手信息，根据hash函数获取散列后下标信息

      //参加学生
    private Student[] students;

    //当前参加人数
    private int num;

    public SchoolSport() {
        this.students = new Student[89];
    }

    public void add(Student student) {

        String key = student.grade.concat(student.classNum);
        if (num < 10) {
            key = key + "0" + num;
        } else {
            key = key + num;
        }
        student.number = key;
        students[hash(key)] = student;
        num++;
    }

    public Student get(String number) {
        return students[hash(number)];
    }

    public int hash(String key) {

        if (StringUtils.isEmpty(key)) {
            return -1;
        }

        //后两位作为数组下标
        String lastStr = key.substring(key.length() - 2);
        return Integer.parseInt(lastStr);
    }

    private static class Student {

        //姓名
        private String name;

        //年级
        private String grade;

        //班级
        private String classNum;

        //编号
        private String number;


        public Student(String name, String grade, String classNum) {
            this.name = name;
            this.grade = grade;
            this.classNum = classNum;
        }

2.Word 文档中单词拼写检查功能是如何实现的？

常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就是 20MB。对于现在的计算机来说，这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。

3.假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？

依次遍历数据，将URL为key， 访问次数为value，放入散列表，并记录最大值。再将最大值数据排序，数据较小则使用桶排序，较大可以使用快速排序。

4.有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？

选择一组数组数据，以字符串数据为key， value为出现次数，存入散列表。再遍历两一个字符串，如果查找散列表数据，如果value大于0，则存在相等字符串。