Tag: 学习笔记

哈希冲突、散列表学习记录

Posted on by Laughing_Lz 
 1/********************************************
 2 * All Rights Reserved By www.laughing.ren
 3 * @author:Laughing_Lz
 4 * @version:2018年11月27日 上午1:07:01
 5 * ******************************************/
 6package ren.laughing.code.Test;
 7
 8import java.util.HashMap;
 9import java.util.LinkedHashMap;
10import java.util.Map;
11import java.util.TreeMap;
12
13public class Hash {
14    class Son {
15        private int age;
16        private String name;
17    }
18
19    /*
20     * ThreadLocalMap 使用了开放寻址法处理hash冲突 数据量小，装载因子小（较于链表更浪费内存空间）
21     * 开放寻址法的数据都存储在数组中，可以有效利用CPU缓存加快查询，而且序列化较为简单。
22     * 删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，
23     * 使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
24     */
25    public static void hash() {
26        // ThreadLocalMap是ThreadLocal的内部类，它是一个Map，key是ThreadLocal的实例变量
27        ThreadLocal<Son> threadLocal = new ThreadLocal<Son>();
28        // 使用链表法解决hash冲突，适用于大对象，大数据量，装载因子可以大于1，使用灵活，可将链表转换为红黑树、跳表等结构。
29        LinkedHashMap<String, Son> linkedHashMap = new LinkedHashMap<>();
30        HashMap<String, Son> map = new HashMap<String, Son>();
31        // hashmap 可修改初始大小，默认为16，装载因子默认0.75
32        HashMap<Object, Object> hashMap = new HashMap<Object, Object>(110);
33    }
34    /*
35     * 设计工业级的散列表，应具有哪些属性？ 1.支持快速查询、插入、删除 2.内存占用合理，不能浪费过多的内存空间
36     * 3.性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况
37     */
38
39    /*
40     * 如何设计工业级的散列表？ 1.设计一个合理的散列函数 2.定义装载因子阈值，并且设计动态扩容策略 3.选择合适的散列冲突解决方法
41     */
42
43    /*
44     * 集合类的带hash的，例如hashmap、hashset、hashtable等。
45     * hashmap中散列函数是key的hashcode与key的hashcode右移16位异或，这是为了把key的高位考虑进去，如果key是0，hash值为0
46     * 。在put的时候，如果表没有初始化，需要初始化下，在计算key的位置的时候很巧妙，使用表的length-1和key的hash值与计算的，
47     * 实际上就是对key的hash值对表长取模，基于hashmap是2的幂次方特性，这种位运算速度更快。如果put后hashmap的数据容量超过了表的容量*
48     * 负载因子，就会自动扩容，默认是两倍，自动扩容方法是将key的hash与表长直接与判断是否有高位，有高位就把这个node放到新表里旧表对应位置加旧表长的地方
49     * 。没有高位就直接是新表旧位置。这是hashmap1.8的处理方法。hashmap1.7还是对key的hash取模。如果是个非常大的数，赋值为integer
50     * .max。hashmap采用的是链地址法结合红黑树解决hash冲突，当桶中链表长度大于8就会将桶中数据结构转化为红黑树。
51     * hashtable默认的初使容量11，负载因子也是0.75，如果要指定初始化hashtable容量最好是给一个素数。
52     * 这是因为放入table的时候需要对表长取模，尽量分散地映射。hashtable通过链地址法解决hash冲突，当数据容量大于数据容量*负载因子自动扩容，
53     * 扩容原表长两倍+1。
54     */
55    /*
56     * TreeMap 使用红黑树的数据结构，好好研究源码
57     */
58    Map<String, String> map = new TreeMap<>();
59}
Views: 704

《SQL必知必会》笔记

Posted on by Laughing_Lz

SQL：

  1. DDL 数据定义语言：用于创建、修改或删除数据库对象，如表、视图、模式、触发器和存储过程等。相关的关键字包括CREATE,ALTER,DROP
  2. DQL数据查询语言：用于数据的检索查询，相关的关键字为SELECT
  3. DML数据操纵语言：用于添加，修改或删除存储在数据库对象中的数据，相关的关键字有INSERT,UPDATE,DELETE
  4. DCL数据控制语言：用于控制访问数据库中特定对象的用户，还可以控制用户对数据库的访问类型，相关的关键字有GRANT,DENY,REVOKE

使用DISTINCT参数，只返回不同的值

SELECT

CONCAT(

v.`vend_name`,

RTRIM(‘ ‘),

v.`vend_country`

) AS ‘拼接后’,

SOUNDEX(v.`vend_address`),

v.`vend_address`,

LEFT(v.`vend_address`,8),

UPPER(v.`vend_city`),

LOWER(v.`vend_city`)

FROM

vendors v ;

— RTRIM去掉右边的所有空格

— LTRIM去掉左边的所有空格

— TRIM去掉左右两边的空格

— LEFT(str,len)返回字符串左边长度的字符

— RIGHT(str,len)返回字符串右边长度的字符

— LOWER(str)将字符串转换为小写

— UPPER(str)将字符串转换为大写

— SOUNDEX()返回字符串的SOUNDEX值

拼接后 soundex(v.`vend_address`) vend_address left(v.`vend_address`,8) upper(v.`vend_city`) lower(v.`vend_city`)

——————– ————————- ————— ———————— ——————– ———————-

Bear EmporiumUSA P62363 500 Park Street 500 Park ANYTOWN anytown

Bears R UsUSA M2363 123 Main Street 123 Main BEAR TOWN bear town

Doll House Inc.USA H2363 555 High Street 555 High DOLLSVILLE dollsville

Fun and GamesEngland G4263 42 Galaxy Road 42 Galax LONDON london

Furball Inc.USA T150 1000 5th Avenue 1000 5th NEW YORK new york

Jouets et oursFrance R5253 1 Rue Amusement 1 Rue Am PARIS paris

SELECT

o.`order_num`,

o.`order_date`

FROM

orders o

WHERE

YEAR(o.`order_date`) = 2012;

— YEAR() 从日期中提取年份

— ABS() 返回一个数的绝对值

— SQRT() 返回一个数的平方

— EXP() 返回一个数的指数值

— PI() 返回圆周率

— COS() 返回一个角度的余弦

— SIN() 返回一个角度的正弦

— TAN() 返回一个角度的正切

order_num order_date

——— ———————

20005 2012-05-01 00:00:00

20006 2012-01-12 00:00:00

20007 2012-01-30 00:00:00

20008 2012-02-03 00:00:00

20009 2012-02-08 00:00:00

聚集函数（操作列，返回一个数）：AVG() COUNT() MAX() MIN() SUM()

均忽略NULL值，不统计

COUNT(*)不会忽略NULL值

MAX()也可返回该列排序的最后一行

MIN()也可返回该列排序的第一行

当不指定GROUP BY时候，所有类型的WHERE子句都可以用HAVING来替代。

差别在于WHERE过滤行，HAVING过滤分组。

SELECT

o.`cust_id`,

COUNT(*) AS orders

FROM

orders o

WHERE o.`cust_id` <> 1000000003

GROUP BY o.`cust_id`

HAVING COUNT(*) >= 2 ;

cust_id orders

———- ——–

1000000001 2

WHERE在数组分组前进行行过滤，HAVING在数据分组后进行分组过滤。

子查询：

  1. 作为子查询的SELECT语句只能查询单个列。
  2. 作为计算字段使用子查询，多数情况需要使用完全限定名，即A.id = B.id，以免混淆列名。

联结表：

FROM A,B

WHERE A.id = B.id

或者

INNER JOIN … ON …（内联结）

 FROM A AS a1, A AS a2

WHERE a1.id = a2.id（自联结）

 对一个表使用通配符（SELECT *），而对其他表的列使用明确的子集来完成。——自然联结 为包含哪些没有关联行的行。——外联结，包括：左外联结：LEFT OUTER JOIN … ON …右外联结：RIGHT OUTER JOIN … ON …全外联结：FULL OUTER JOIN … ON …

复杂查询的方法：

  1. 子查询
  2. 联结表

通常处理联结比处理子查询快得多。

组合查询：

  1. UNION 必须由两条或两条以上SELECT语句组成，语句之间用关键字UNION分隔
  2. UNION中的每个查询必须包含相同的列、表达式或聚集函数（不过，各个列不必以相同的次序列出）
  3. 列数据必须兼容：类型不必完全相同，但必须是DBMS可以隐含转换的类型（例如，不同的数值或日期类型）

另外，UNION从查询结果集中自动去除了重复行，若要返回所有的匹配行，应使用UNION ALL（不可用WHERE代替）

插入数据：

1、INSERT INTO A(id,name,…) VALUES(‘1′,’xiaoli’,…);

这种方法可插入完整行，也可插入行的一部分，前提是表的定义允许在INSERT操作中省略某些列，省略的列必须满足：

  1. 该列定义为允许NULL值（无值或空值）
  2. 在表定义中给出默认值。

2、INSERT INTO A(id,name,…) SELECT id,name,… FROM B；

插入检索出的数据，注意这里不一定要求列名匹配，它使用的是列的位置。

3、CREATE TABLE B AS SELECT * FROM A;

从一张表复制到另一张表。

更新数据：

UPDATE A SET id = ‘…’, name = ‘…’ WHERE …

删除数据：

DELETE FROM A WHERE id = ‘…’;

若从表中删除所有行，可用TRUNCATE TABLE A语句，速度更快，因为不记录数据的变动。

DELETE和TRUNCATE区别

1.DELETE

・DML语言

・可以回退

・可以有条件的删除

DELETE FROM 表名

WHERE 条件

2.TRUNCATE TABLE

・DDL语言

・无法回退

・默认所有的表内容都删除

・删除速度比delete快。

主键外键的写法：

CREATE TABLE Orders1 (

order_num CHAR(10) NOT NULL PRIMARY KEY, — 指定主键

cust_id CHAR(10) NOT NULL,

CONSTRAINT fk_PerOrders FOREIGN KEY (cust_id) REFERENCES customers (cust_id) — 添加外键

) ;

ALTER TABLE Orders1

ADD FOREIGN KEY (cust_id) REFERENCES customers (cust_id); — 添加外键

ALTER TABLE Orders1

ADD CONSTRAINT fk_PerOrders FOREIGN KEY (cust_id) REFERENCES customers (cust_id); — 添加外键

另外还有，唯一约束UNIQUE，检查约束CHECK，定义参考 <http://www.w3school.com.cn/sql/sql_check.asp>

★唯一约束和主键约束的区别：

  1. 每个表可包含多个唯一约束，但只能有一个主键。
  2. 唯一约束列可包含NULL值。
  3. 唯一约束列可修改或更新。
  4. 唯一约束列的值可重复使用。
  5. 和主键不一样，唯一约束不能用来定义外键。
Views: 977