java面试题1

一.hashMap底层以及实现原理是什么。

介绍jdk1.8以后的内容：HashMap底层实现了Map接口，数据结构的存储由数组+链表变成数组+链表+红黑树。

看一下底层代码：

 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;

        //判断table是否初始化，否则初始化

        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //计算存储索引的位置，如果位置上没有元素，则直接赋值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判断连表是否是红黑树
            else if (p instanceof TreeNode)
               //红黑树对象操作
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
               //链表操作
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //链表长度为8,那么转成红黑树存储(下面会给出解释)
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //key存在,直接覆盖
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //记录修改次数
        ++modCount;
        //判断是否需要扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

小结:

1.如果此map没有数据,那么直接执行resize()方法.

2.如果要插入的键值对的位置上刚好没有元素,直接封装成Node对象,并放入这个位置上.

3.如果发生碰撞,判断此位置是链表还是红黑树,

1)如果是红黑树,将k-v直接插入.

2)如果是链表,那就要遍历链表:

a:如果是链表最后一个位置,直接插到链表尾部.

b:插入完,如果链表的长度大于8,那么转成红黑树存储,因为链表的平均查询速度是n/2,而红黑树是log(n),长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，这才有转换为树的必要。链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。所以大于8时转换成树.

4.如果键重复,直接break跳出.

5.判断是否要扩容

6.返回

总结:

HashMap是通过Hash算法来决定Map中的key存储,如果通过key计算的hash值这个位置有元素,将采用链表形式存储元素.HashMap底层中没有synchronize,所以是线程不安全的,而HashTable底层有synchronize所以是线程安全的,也因此hashMap比HashTable速度快;HashMap的键值对允许为空,但hashTable不允许.

二:MySQL有几种索引.

索引分单列索引和组合索引.索引要应用在查询语句的条件中(一般为where条件),索引在MySQL中也有一张表,这张表保存了索引和主键并指向实体表的记录,所以虽然索引提高了表的查询速度但是却降低了表的更新速度,在进行insert,update,delete时,数据库不仅要保存数据,还要更新索引表,所以索引不是越多越好.

MySQL目前有FUllTEXT,BTREE,RTREE,HASH这四种索引.

1.FULLTEXT 全文索引,MyISAM引擎(MySQL5.5版本一下有)支持,可以在alter table ,create table,create index中使用,不过目前只支持char,varchar,text类型的列上可以创建全文索引.

2.HASH hash索引,类似于键值对的形式,可以一次定位,不像树形索引那样要组层查找,所以速度很快,但是它只在in,=,<=,>=的条件下效率高,对于范围查找,排序及组合索引仍然效率不高.

3.BTREE btree索引是一种将索引值按照一定的计算方式存储到树形结构中,每次查询都是先从root开始,依次遍历node,获取leaf(叶子,也就是值),是MySQL里默认和最常用的索引.

4.RTREE 此索引很少使用,只支持geometry类型的数据.

java面试题1

推荐阅读