QuickPassHBase

快速上手HBase

[TOC]

⚙ 1. HBase简介

1.1 HBase的定义

Apache HBase 是以 HDFS 为数据存储的,一种分布式、可扩展的 NoSQL 数据库。

HBase 的设计理念依据 Google 的 BigTable 论文,论文中对于数据模型的首句介绍。

BigTable是一个稀疏的、分布式的、持久的多维排序映射(Map)。该映射由行键、列键和时间戳索引作为键(Key),映射中的每个值(Value)都是一个未解释的字节数组。

HBase 使用与 BigTable 非常相似的数据模型。用户将数据行存储在带标签的表中。数据行具有可排序的键和任意数量的列。该表存储稀疏,因此如果用户喜欢,同一表中的行可以具有疯狂变化的列。

1.2 HBase的数据模型

1.2.1 HBase 的逻辑结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
{
"row_key1": {
"personal_info": {
"name": "ZhangSan",
"city": "Beijing",
"phone": "156****0000"
},
"office_info": {
"tel": "010-1234567",
"address": "Shandong"
}
},
"row_key11": {
"personal_info": {
"city": "Shanghai",
"phone": "133****0000"
},
"office_info": {
"tel": "010-1234567",
}
},
"row_key2": {
...
}
}
列族→ personal_info office_info
RowKey↓ name city phone tel address
row_key1 ZhangSan Beijing 156****0000 010-1234567 Shandong
row_key11 Shanghai 131****0000 010-1234567
row_key2 ... ... ... ... ...

在上面的表格中:

  • personal_infooffice_info称为列族
  • namecityphoneteladdress称为
  • row_key1row_key11称为行键
  • 将一整张大表按照进行拆分,拆分为多个表,拆分后的每个表称为**块(Region)**,用于实现分布式结构。
  • 将一整张大表按照列族进行拆分,拆分为多个**存储(Store)**,用于在底层存储到不同的文件夹中,便于文件对应。

存储数据稀疏,数据存储多维,不同的行具有不同的列。数据存储整体有序,按照RowKey的字典序排列,RowKey为一个Byte数组。

1.2.2 HBase 的物理结构

物理存储结构即为数据映射关系,而在概念视图的空单元格,底层实际根本不存储。

在HDFS中划分好的存储Store如下:

personal_info
RowKey name city phone
row_key1 ZhangSan Beijing 156****0000
row_key11 Shanghai 131****0000
row_key2 ... ... ...

其底层一定是以映射(Map)的方式进行存储的,格式为**(Key, Value)Value一定是“ZhangSan”**这种字段。那么Key是什么呢?

为了确定Value值**”ZhangSan”,我们需要用Key对应到Value**,于是得到存储如下:

Row Key Column Family Column Qualifier Timestamp Type Value
row_key1 personal_info name t1 Put ZhangSan
row_key1 personal_info city t2 Put Beijing
row_key1 personal_info phone t3 Put 156****0000
row_key1 personal_info phone t4 Put 156****0001
row_key1 personal_info phone t5 Delete 156****0001

因为 HDFS 是无法修改数据的,而 HBase 需要修改数据,那么就需要解决这一问题,于是就有了**时间戳(Timestamp)**。不同版本(version)的数据根据 Timestamp 进行区分,读取数据默认读取最新的版本。

在上面的表格中,t4相对于t3来说就是进行了修改,将t3时的**phone156****0000修改为t4时的156****0001,读取时默认读取t4时的phone**值,通过这种方式完成了修改。

同样的,我们也不好删除数据,因此我们只需要插入一条**Type**为Delete的数据即可。

1.2.3 数据模型
  • Name Space 命名空间

    类似于关系型数据库的 Database 概念,每个命名空间下有多个表。HBase 两个自带的命名空间,分别是 hbasedefaulthbase 中存放的是 HBase 内置的表,default表是用户默认使用的命名空间。

  • Table

    类似于关系型数据库的概念。不同的是,HBase 定义表时只需要声明列族即可,不需要声明具体的列。因为数据存储时稀疏的,所有往HBase写入数据时,字段可以动态、按需指定。因此,和关系型数据库相比,HBase能够轻松应对字段变更的场景。

    需要注意的是,列族的存在是动态添加列(或称字段)的基础。

  • Row

    HBase 表中的每行数据都由*一个行键(RowKey)多个列(Column)组成,数据是按照 RowKey的字典顺序存储的,*并且查询数据时只能根据 RowKey进行检索**,所以RowKey的设计十分重要。

  • Column

    HBase 中的每个列都由列族(Column Family)列限定符(Column Qualifier)进行限定,例如info:name, info:age。建表时,只需指明列族,而列限定符无需预先定义。列限定符听起来很高端,其实就是列名的意思。

  • Time Stamp

    用于标识数据的**不同版本(Version)**,每条数据写入时,系统会自动为其加上该字段,其值为写入 HBase 的时间。

  • Cell

    {rowkey, Column Family: Column Qualifier, Timestamp} 唯一确定的单元,Cell 中的数据全部是字节码形式存储。

1.3 HBase 基本架构

HBase基本架构
  • Master

    主要进程,具体实现类为HMaster,通常部署在NameNode上。

    主要功能:负责通过 ZK 监控 RegionServer 进程状态,同时是所有元数据变化的接口,内部启动监控执行 region 的故障转移和拆分的线程。

    功能的详细描述

    • 管理元数据表格 hbase:meta:接收用户对表格创建、修改、删除的命令并执行。

    • 监控 RegionServer 是否需要进行负载均衡故障转移Region拆分。通过启动多个后台线程监控实现上述功能:

      • LoadBalancer 负载均衡器

        周期性监控 region分布在 RegionServer 上面是否均衡,由参数 hbase.balancer.period控制周期时间,默认5分钟。

      • CatalogJanitor元数据管理器

        定期检查和清理hbase:meta中的数据。

      • MasterProcWAL Master 预写日志处理器

        把Master需要执行的任务记录到预写日志WAL中,如果Master宕机,则让BackupMaster继续操作。

  • RegionServer

    主要进程,具体实现类为HRegionServer,通常部署在DataNode上。

    功能:主要负责数据 Cell 的处理,同时在执行区域的拆分和合并的时候,由 RegionServer 来实际执行。

    功能的详细描述

    • 负责数据 Cell 的处理,例如写入数据put,查询数据get等。
    • 拆分合并 region 的实际执行者,有 Master 监控,有RegionServer 执行。
  • ZooKeeper

    HBase 通过 ZooKeeper 来做 Master的高可用、记录 RegionServer 的部署信息、并且存储有 meta 表的位置信息。
    HBase 对于数据的读写操作时是直接访问 ZooKeeper 的,在 2.3 版本推出 Master Registry 模式,客户端可以直接访问 Master。使用此功能,会加大对 Master的压力,减轻对 ZooKeeper 的压力。

  • HDFS

    HDFS 为 HBase 提供最终的底层数据存储服务,同时为 HBase 提供高容错的支持。

上图中的Region由三个RegionServer随机管理,尽量均衡。表名hbase:meta是一个特例,他存储在HDFS,但是由Master管理。

🔧 2. 快速上手

2.1 安装部署

2.1.1 分布式部署
  1. 至少 3 台虚拟机

    1
    2
    3
    hadoop101
    hadoop102
    hadoop103
  2. 保证 ZooKeeper 正常部署,并且启动 ZooKeeper

    1
    zkServer.sh start
  3. 保证 Hadoop 正常部署,并且启动 Hadoop

    1
    start-dfs.sh
  4. 配置 HBase 环境

    ① 下载 HBase 安装包(压缩包),这里假设为hbase-2.4.11-bin.tar.gz

    ② 解压 HBase 安装包到一个文件夹

    1
    tar -zxvf /path/to/hbase-2.4.11-bin.tar.gz -C /path/to/module

    ③ 在用户目录下,添加用户环境变量

    1
    vim .bashrc
    1
    2
    3
    #HBase_HOME
    export HBASE_HOME = /path/to/module/hbase-2.4.11
    export PATH = $PATH:$HBASE_HOME/bin

    ④ 使环境变量生效

    1
    source .bashrc

    ⑤ 修改配置文件

    • hbase-env.sh

      1
      2
      3
      # 表示是否需要 HBase 管理维护一个自带的 ZooKeeper, 默认为 true
      # 我们需要使用本机已经配置好的 ZooKeeper, 所以修改为 False
      export HBASE_MANAGES_ZK = false
    • hbase-site.xml

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      <?xml version="1.0"?>
      <?xml-stylesheet type="text/xsl" href="configuration.xsl"?>
      <configuration>
      <!-- ZooKeeper的地址 -->
      <property>
      <name>hbase.zookeeper.quorum</name>
      <value>hadoop101,hadoop102,hadoop103</value>
      </property>

      <!-- HBase数据在HDFS中的存放路径 -->
      <property>
      <name>hbase.rootdir</name>
      <value>hadoop101:8020/hbase</value>
      </property>

      <!-- HBase的运行模式 -->
      <!-- false为单机模式, HBase和ZooKeeper会运行在同一个JVM虚拟机中 -->
      <!-- true 为分布式模式 -->
      <property>
      <name>hbase.cluster.distributed</name>
      <value>true</value>
      </property>

      <!-- ZooKeeper快照的存储位置 -->
      <!-- 这里替换为自己的 /path/to/ZooKeeperDir -->
      <property>
      <name>hbase.zookeeper.property.dataDir</name>
      <value>/opt/module/zookeeper-3.4.6/data</value>
      </property>

      <!-- HBase 安全模式 -->
      <!-- 在分布式模式下, 设置为 false -->
      <property>
      <name>hbase.unsafe.stream.capability.enforce</name>
      <value>false</value>
      </property>
      </configuration>
    • regionservers

      1
      2
      3
      hadoop101
      hadoop102
      hadoop103

    ⑥ 解决 log4j 不兼容的问题,移除 HBase或者 Hadoop.jar

    ⑦ 使用 scp 命令同步 HBase 配置,需要提前设置好免密登录。或者使用 xsync

  5. 启动 HBase 服务

    • 单点启动

      1
      2
      3
      4
      #单点启动HMaster
      hbase-daemon.sh start master
      #单点启动HRegionServer
      hbase-daemon.sh start regionserver
    • 集群启动

      1
      start-hbase.sh
    • 停止服务

      1
      stop-hbase.sh
2.1.2 高可用服务
  1. 如果 HBase 已经启动,先关闭HBase

    1
    stop-hbase.sh
  2. 添加配置文件 backup-masters

    1
    2
    3
    #使用touch命令或者echo命令均可
    touch /path/to/hbase-2.1.4/conf/backup-masters
    vim /path/to/hbase-2.1.4/conf/backup-masters

    添加内容:hadoop102

  3. 使用 scp 命令分发配置文件

  4. 启动HBase,正常启动进程如下:

    1
    2
    3
    hadoop101 -> HMaster HRegionServer
    hadoop102 -> HMaster HRegionServer
    hadoop103 -> HRegionServer

    其中,hadoop101HMaster 先启动作为主节点,hadoop102HMaster后启动,作为**备用节点(Backup-Master)**。

2.2 使用操作

2.2.1 Shell操作

使用命令 hbase shell 启动 HBase 的 Shell 命令界面,所有命令均可以使用 help 查到。

当我们在 hbase shell中输入help命令时,将会弹出HBase的使用提示:

1
hbase shell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
hbase(main):001:0> help
HBase Shell, version 2.1.8, rd8333e556c8ed739cf39dab58ddc6b43a50c0965, Tue Nov 19 15:29:04 UTC 2019
Type 'help "COMMAND"', (e.g. 'help "get"' -- the quotes are necessary) for help on a specific command.
Commands are grouped. Type 'help "COMMAND_GROUP"', (e.g. 'help "general"') for help on a command group.

COMMAND GROUPS:
Group name: general
Commands: processlist, status, table_help, version, whoami

Group name: ddl
Commands: alter, alter_async, alter_status, clone_table_schema, create, describe, disable, disable_all, drop, drop_all, enable, enable_all, exists, get_table, is_disabled, is_enabled, list, list_regions, locate_region, show_filters

Group name: namespace
Commands: alter_namespace, create_namespace, describe_namespace, drop_namespace, list_namespace, list_namespace_tables

Group name: dml
Commands: append, count, delete, deleteall, get, get_counter, get_splits, incr, put, scan, truncate, truncate_preserve

Group name: tools
Commands: assign, balance_switch, balancer, balancer_enabled, catalogjanitor_enabled, catalogjanitor_run, catalogjanitor_switch, cleaner_chore_enabled, cleaner_chore_run, cleaner_chore_switch, clear_block_cache, clear_compaction_queues, clear_deadservers, close_region, compact, compact_rs, compaction_state, flush, hbck_chore_run, is_in_maintenance_mode, list_deadservers, major_compact, merge_region, move, normalize, normalizer_enabled, normalizer_switch, split, splitormerge_enabled, splitormerge_switch, stop_master, stop_regionserver, trace, unassign, wal_roll, zk_dump

Group name: replication
Commands: add_peer, append_peer_exclude_namespaces, append_peer_exclude_tableCFs, append_peer_namespaces, append_peer_tableCFs, disable_peer, disable_table_replication, enable_peer, enable_table_replication, get_peer_config, list_peer_configs, list_peers, list_replicated_tables, remove_peer, remove_peer_exclude_namespaces, remove_peer_exclude_tableCFs, remove_peer_namespaces, remove_peer_tableCFs, set_peer_bandwidth, set_peer_exclude_namespaces, set_peer_exclude_tableCFs, set_peer_namespaces, set_peer_replicate_all, set_peer_serial, set_peer_tableCFs, show_peer_tableCFs, update_peer_config

Group name: snapshots
Commands: clone_snapshot, delete_all_snapshot, delete_snapshot, delete_table_snapshots, list_snapshots, list_table_snapshots, restore_snapshot, snapshot

Group name: configuration
Commands: update_all_config, update_config

Group name: quotas
Commands: list_quota_snapshots, list_quota_table_sizes, list_quotas, list_snapshot_sizes, set_quota

Group name: security
Commands: grant, list_security_capabilities, revoke, user_permission

Group name: procedures
Commands: list_locks, list_procedures

Group name: visibility labels
Commands: add_labels, clear_auths, get_auths, list_labels, set_auths, set_visibility

Group name: rsgroup
Commands: add_rsgroup, balance_rsgroup, get_rsgroup, get_server_rsgroup, get_table_rsgroup, list_rsgroups, move_namespaces_rsgroup, move_servers_namespaces_rsgroup, move_servers_rsgroup, move_servers_tables_rsgroup, move_tables_rsgroup, remove_rsgroup, remove_servers_rsgroup

SHELL USAGE:
Quote all names in HBase Shell such as table and column names. Commas delimit
command parameters. Type <RETURN> after entering a command to run it.
Dictionaries of configuration used in the creation and alteration of tables are
Ruby Hashes. They look like this:

{'key1' => 'value1', 'key2' => 'value2', ...}

and are opened and closed with curley-braces. Key/values are delimited by the
'=>' character combination. Usually keys are predefined constants such as
NAME, VERSIONS, COMPRESSION, etc. Constants do not need to be quoted. Type
'Object.constants' to see a (messy) list of all constants in the environment.

If you are using binary keys or values and need to enter them in the shell, use
double-quote'd hexadecimal representation. For example:

hbase> get 't1', "key\x03\x3f\xcd"
hbase> get 't1', "key\003\023\011"
hbase> put 't1', "test\xef\xff", 'f1:', "\x01\x33\x40"

The HBase shell is the (J)Ruby IRB with the above HBase-specific commands added.
For more on the HBase Shell, see http://hbase.apache.org/book.html

根据上述信息,我们可以进一步的操作 HBase 数据库。我们实际开发中常用的**命令组(COMMAND GROUPS)**有:generalnamespaceddldml等,下面依次介绍这些内容:

  • 通用命令 general

    • 查看 HBase 状态 status,提供 HBase 的状态,如服务器的数量等

      1
      2
      3
      hbase(main):001:0> status
      1 active master, 0 backup masters, 1 servers, 0 dead, 4.0000 average load
      Took 0.5268 seconds
    • 查看 HBase 版本 version,提供正在使用 HBase 版本

      1
      2
      3
      hbase(main):002:0> version
      2.1.8, rd8333e556c8ed739cf39dab58ddc6b43a50c0965, Tue Nov 19 15:29:04 UTC 2019
      Took 0.0002 seconds
    • 表引用命令提供帮助 table_help

    • 提供有关用户的信息 whoami

      1
      2
      3
      4
      hbase(main):003:0> whoami
      nilera (auth:SIMPLE)
      groups: nilera
      Took 0.0283 seconds
  • 操作命名空间 Namespace

    **命名空间(Namespace)**,相当于MySQL数据库中的DataBase。Namespace 命令包括:alter namespacecreate_namespacedescribe_namespacedrop_namespacelist_namespacelist_namespace_tables。下面将对一些常用命令进行介绍:

    • 查看全部命名空间 list_namespace

      1
      2
      3
      4
      5
      6
      hbase(main):001:0> list_namespace
      NAMESPACE
      default
      hbase
      2 row(s)
      Took 0.5484 seconds
    • 创建命名空间 create_namespace

      用法:create_namespace 'ns'

      1
      2
      3
      4
      5
      6
      7
      8
      9
      hbase(main):001:0> create_namespace 'bigdata'
      Took 0.0432 seconds
      hbase(main):002:0> list_namespace
      NAMESPACE
      bigdata
      default
      hbase
      3 row(s)
      Took 0.0224 seconds
    • 删除命名空间 drop_namespace

      用法:drop_namespace 'ns',删除命名空间时,命名空间必须为空。

    • 查看命名空间 describe_namespace

      用法:describe_namespace 'ns'

      1
      2
      3
      4
      5
      hbase(main):001:0> describe_namespace 'bigdata'
      DESCRIPTION
      {NAME => 'bigdata'}
      Took 0.0068 seconds
      => 1
    • 查看命名空间下的表 list_namespace_tables

      用法:list_namespace_tables 'ns'

      1
      2
      3
      4
      5
      6
      7
      hbase(main):001:0> list_namespace_tables 'default'
      TABLE
      logs
      user
      2 row(s)
      Took 0.3790 seconds
      => ["logs", "user"]
  • 数据定义语言 ddl

    DDL(Data Definition Language)数据定义语言,主要是进行定义/改变表的结构、数据类型、表之间的链接等操作。ddl 相关命令如下:alteralter_asyncalter_statusclone_table_schemacreatedescribedisabledisable_alldropdrop_allenableenable_allexistsget_tableis_disabledis_enabledlistlist_regionslocate_regionshow_filters。下面将对一些常用命令进行介绍:

    • 创建表 create

      常见用法:

      create 'ns:tb', {NAME => 'cf', VERSIONS => 5}

      ​ 在命名空间 ns 下,创建一张表 tb,定义一个列族 cf

      ② 当在默认命名空间default下创建表时,可以省略 ns

      create 'tb', 'cf1', 'cf2'

      ​ 在默认命名空间default下,创建一张表tb,并定义两个列族 cf1cf2

      create 'tb', {NAME => 'cf1', VERSIONS => 5}, {NAME => 'cf2', VERSIONS => 5}

      ​ 在默认命名空间default下,创建一张表tb,并定义两个列族 cf1cf2,并同时指定两个列族的版本为 5

      1
      2
      3
      4
      hbase(main):001:0> create 'bigdata:person', {NAME => 'name', VERSIONS => 5}, {NAME => 'msg', VERSIONS => 5}
      Created table bigdata:person
      Took 1.5638 seconds
      => Hbase::Table - bigdata:person
    • 查看表的详细信息 describe

      用法describe 'tb'

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      hbase(main):010:0> describe 'bigdata:person'
      Table bigdata:person is ENABLED
      bigdata:person
      COLUMN FAMILIES DESCRIPTION
      {NAME => 'msg', VERSIONS => '5', EVICT_BLOCKS_ON_CLOSE => 'false', NEW_VERSION_BEHAVIOR => 'false', KEEP_DELETED_CELLS => 'FALSE', CACHE_DATA_ON_WRITE => 'fal
      se', DATA_BLOCK_ENCODING => 'NONE', TTL => 'FOREVER', MIN_VERSIONS => '0', REPLICATION_SCOPE => '0', BLOOMFILTER => 'ROW', CACHE_INDEX_ON_WRITE => 'false', IN
      _MEMORY => 'false', CACHE_BLOOMS_ON_WRITE => 'false', PREFETCH_BLOCKS_ON_OPEN => 'false', COMPRESSION => 'NONE', BLOCKCACHE => 'true', BLOCKSIZE => '65536'}
      {NAME => 'name', VERSIONS => '5', EVICT_BLOCKS_ON_CLOSE => 'false', NEW_VERSION_BEHAVIOR => 'false', KEEP_DELETED_CELLS => 'FALSE', CACHE_DATA_ON_WRITE => 'fa
      lse', DATA_BLOCK_ENCODING => 'NONE', TTL => 'FOREVER', MIN_VERSIONS => '0', REPLICATION_SCOPE => '0', BLOOMFILTER => 'ROW', CACHE_INDEX_ON_WRITE => 'false', I
      N_MEMORY => 'false', CACHE_BLOOMS_ON_WRITE => 'false', PREFETCH_BLOCKS_ON_OPEN => 'false', COMPRESSION => 'NONE', BLOCKCACHE => 'true', BLOCKSIZE => '65536'}
      2 row(s)
      Took 0.1536 seconds
    • 修改表 alter

      表名创建时写的所有和列族相关的信息,都可以后续通过alter修改,包括增加删除列族。

      ① 增加列族和修改信息都使用覆盖的方法

      ​ 修改列族的版本,VERSIONS => 6

      1
      2
      3
      4
      5
      hbase(main):001:0> alter 'bigdata:person', NAME => 'name', VERSIONS => 6
      Updating all regions with the new schema...
      1/1 regions updated.
      Done.
      Took 4.0145 seconds

      ​ 添加列族 tel

      1
      2
      3
      4
      5
      hbase(main):002:0> alter 'bigdata:person', NAME => 'tel', VERSIONS => 6
      Updating all regions with the new schema...
      1/1 regions updated.
      Done.
      Took 2.4498 seconds

      ​ 查看修改后的数据:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      hbase(main):003:0> describe 'bigdata:person'
      Table bigdata:person is ENABLED
      bigdata:person
      COLUMN FAMILIES DESCRIPTION
      {NAME => 'msg', VERSIONS => '6', EVICT_BLOCKS_ON_CLOSE => 'false', NEW_VERSION_BEHAVIOR => 'false', KEEP_DELETED_CELLS => 'FALSE', CACHE_DATA_ON_WRITE => 'fal
      se', DATA_BLOCK_ENCODING => 'NONE', TTL => 'FOREVER', MIN_VERSIONS => '0', REPLICATION_SCOPE => '0', BLOOMFILTER => 'ROW', CACHE_INDEX_ON_WRITE => 'false', IN
      _MEMORY => 'false', CACHE_BLOOMS_ON_WRITE => 'false', PREFETCH_BLOCKS_ON_OPEN => 'false', COMPRESSION => 'NONE', BLOCKCACHE => 'true', BLOCKSIZE => '65536'}

      {NAME => 'name', VERSIONS => '5', EVICT_BLOCKS_ON_CLOSE => 'false', NEW_VERSION_BEHAVIOR => 'false', KEEP_DELETED_CELLS => 'FALSE', CACHE_DATA_ON_WRITE => 'fa
      lse', DATA_BLOCK_ENCODING => 'NONE', TTL => 'FOREVER', MIN_VERSIONS => '0', REPLICATION_SCOPE => '0', BLOOMFILTER => 'ROW', CACHE_INDEX_ON_WRITE => 'false', I
      N_MEMORY => 'false', CACHE_BLOOMS_ON_WRITE => 'false', PREFETCH_BLOCKS_ON_OPEN => 'false', COMPRESSION => 'NONE', BLOCKCACHE => 'true', BLOCKSIZE => '65536'}

      {NAME => 'tel', VERSIONS => '6', EVICT_BLOCKS_ON_CLOSE => 'false', NEW_VERSION_BEHAVIOR => 'false', KEEP_DELETED_CELLS => 'FALSE', CACHE_DATA_ON_WRITE => 'fal
      se', DATA_BLOCK_ENCODING => 'NONE', TTL => 'FOREVER', MIN_VERSIONS => '0', REPLICATION_SCOPE => '0', BLOOMFILTER => 'ROW', CACHE_INDEX_ON_WRITE => 'false', IN
      _MEMORY => 'false', CACHE_BLOOMS_ON_WRITE => 'false', PREFETCH_BLOCKS_ON_OPEN => 'false', COMPRESSION => 'NONE', BLOCKCACHE => 'true', BLOCKSIZE => '65536'}
      3 row(s)
      Took 0.0795 seconds

      ② 删除列族

      ​ 删除列族可以用以下两种方式:

      1
      2
      3
      4
      5
      hbase(main):001:0> alter 'bigdata:person', NAME => 'tel', METHOD => 'delete'
      Updating all regions with the new schema...
      1/1 regions updated.
      Done.
      Took 2.1046 seconds
      1
      2
      3
      4
      5
      hbase(main):002:0> alter 'bigdata:person', 'delete' => 'msg'
      Updating all regions with the new schema...
      1/1 regions updated.
      Done.
      Took 2.9721 seconds

      ​ 然后查询修改后的数据:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      hbase(main):003:0> describe 'bigdata:person'
      Table bigdata:person is ENABLED
      bigdata:person
      COLUMN FAMILIES DESCRIPTION
      {NAME => 'name', VERSIONS => '5', EVICT_BLOCKS_ON_CLOSE => 'false', NEW_VERSION_BEHAVIOR => 'false', KEEP_DELETED_CELLS => 'FALSE', CACHE_DATA_ON_WRITE => 'fa
      lse', DATA_BLOCK_ENCODING => 'NONE', TTL => 'FOREVER', MIN_VERSIONS => '0', REPLICATION_SCOPE => '0', BLOOMFILTER => 'ROW', CACHE_INDEX_ON_WRITE => 'false', I
      N_MEMORY => 'false', CACHE_BLOOMS_ON_WRITE => 'false', PREFETCH_BLOCKS_ON_OPEN => 'false', COMPRESSION => 'NONE', BLOCKCACHE => 'true', BLOCKSIZE => '65536'}
      1 row(s)
      Took 0.0391 seconds
    • 禁用表 disable

      用法disable 'ns:tb'disable 'tb'

      1
      2
      hbase(main):001:0> disable 'bigdata:person'
      Took 0.9384 seconds
    • 删除表 drop

      用法drop 'ns:tb'drop 'tb',删除表时需要保证表是禁用的,否则会出现以下错误:

      1
      2
      3
      4
      5
      6
      7
      hbase(main):001:0> drop 'bigdata:person'

      ERROR: Table bigdata:person is enabled. Disable it first.

      For usage try 'help "drop"'

      Took 0.0248 seconds

      ​ 禁用表后再删除表:

      1
      2
      hbase(main):001:0> drop 'bigdata:person'
      Took 1.7106 seconds
  • 数据操纵语言 dml

    DML(Data Manipulation Language)数据操纵语言,主要是对数据进行增加、删除、修改操作。

    • 写入数据 put

      HBase 中如果想要写入数据,只能添加结构中最底层的 Cell。可以手动写入时间戳指定 Cell 的版本,推荐不写,默认使用当前的系统时间。如果重复写入相同 rowKey,相同列的数据,会写入多个版本进行覆盖。所以他同时兼具写入修改的功能。

      用法

      put 'ns:tb', 'rk', 'col', 'value'

      ​ 向命名空间ns中的tb表中的行键为rk,列为col的位置写入值value。其中colcf:col(即列族:列名)的格式。

      ​ 如果重复向相同行号rk,相同col写数据,则会进行覆盖。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      hbase(main):001:0> put 'bigdata:student', '1001', 'info:name', 'zhangsan'
      Took 0.2415 seconds
      hbase(main):002:0> put 'bigdata:student', '1001', 'info:name', 'lisi'
      Took 0.0121 seconds
      hbase(main):003:0> put 'bigdata:student', '1001', 'info:name', 'wangwu'
      Took 0.0342 seconds

      hbase(main):004:0> put 'bigdata:student', '1002', 'info:name', 'zhaoliu'
      Took 0.0082 seconds
      hbase(main):005:0> put 'bigdata:student', '1003', 'info:age', '10'
      Took 0.0050 seconds
      hbase(main):006:0> put 'bigdata:student', '1003', 'info:sex', 'male'
      Took 0.0054 seconds

      put 't1', 'r1', 'c1', 'value'用法同上。

    • 读取数据 get/scan

      读取数据的方法有两个:getscan

      • get最大范围是一行数据,也可以进行列的过滤,读取数据的结果为多行 Cell

      • scan是扫描数据,能够读取多行数据,不建议扫描过多数据,推荐使用 startRowstopRow 来控制读取的数据,默认范围左闭右开。

      get命令

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      Some examples:
      hbase> t.get 'r1' #查看'r1'的数据
      hbase> t.get 'r1', {TIMERANGE => [ts1, ts2]}
      hbase> t.get 'r1', {COLUMN => 'c1'} #过滤单列, 只显示 'c1'
      hbase> t.get 'r1', {COLUMN => ['c1', 'c2', 'c3']} #过滤多列, 只显示 'c1', 'c2', 'c3'
      hbase> t.get 'r1', {COLUMN => 'c1', TIMESTAMP => ts1}
      hbase> t.get 'r1', {COLUMN => 'c1', TIMERANGE => [ts1, ts2], VERSIONS => 4}
      hbase> t.get 'r1', {COLUMN => 'c1', TIMESTAMP => ts1, VERSIONS => 4}
      hbase> t.get 'r1', {FILTER => "ValueFilter(=, 'binary:abc')"}
      hbase> t.get 'r1', 'c1'
      hbase> t.get 'r1', 'c1', 'c2'
      hbase> t.get 'r1', ['c1', 'c2']
      hbase> t.get 'r1', {CONSISTENCY => 'TIMELINE'}
      hbase> t.get 'r1', {CONSISTENCY => 'TIMELINE', REGION_REPLICA_ID => 1}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      hbase(main):001:0> get 'bigdata:student', '1001'
      COLUMN CELL
      info:name timestamp=1717580289267, value=wangwu
      1 row(s)
      Took 0.0645 seconds

      hbase(main):002:0> get 'bigdata:student', '1001', {COLUMN => 'info:name'}
      COLUMN CELL
      info:name timestamp=1717580289267, value=wangwu
      1 row(s)
      Took 0.0107 seconds

      hbase(main):003:0> get 'bigdata:student', '1003', {COLUMN => 'info:age'}
      COLUMN CELL
      info:age timestamp=1717580366636, value=10
      1 row(s)
      Took 0.0185 seconds

      scan 命令

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      Some examples:
      hbase> scan 'hbase:meta'
      hbase> scan 'hbase:meta', {COLUMNS => 'info:regioninfo'}
      hbase> scan 'ns1:t1', {COLUMNS => ['c1', 'c2'], LIMIT => 10, STARTROW => 'xyz'}
      hbase> scan 't1', {COLUMNS => ['c1', 'c2'], LIMIT => 10, STARTROW => 'xyz'}
      hbase> scan 't1', {COLUMNS => 'c1', TIMERANGE => [1303668804000, 1303668904000]}
      hbase> scan 't1', {REVERSED => true}
      hbase> scan 't1', {ALL_METRICS => true}
      hbase> scan 't1', {METRICS => ['RPC_RETRIES', 'ROWS_FILTERED']}
      hbase> scan 't1', {ROWPREFIXFILTER => 'row2', FILTER => "
      (QualifierFilter (>=, 'binary:xyz')) AND (TimestampsFilter ( 123, 456))"}
      hbase> scan 't1', {FILTER =>
      org.apache.hadoop.hbase.filter.ColumnPaginationFilter.new(1, 0)}
      hbase> scan 't1', {CONSISTENCY => 'TIMELINE'}
      hbase> scan 't1', {ISOLATION_LEVEL => 'READ_UNCOMMITTED'}
      hbase> scan 't1', {MAX_RESULT_SIZE => 123456}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      hbase(main):001:0> scan 'bigdata:student'
      ROW COLUMN+CELL
      1001 column=info:name, timestamp=1717580289267, value=wangwu
      1002 column=info:name, timestamp=1717580320927, value=zhaoliu
      1003 column=info:age, timestamp=1717580366636, value=10
      1003 column=info:sex, timestamp=1717581149533, value=male
      3 row(s)
      Took 0.0338 seconds

      hbase(main):025:0> scan 'bigdata:student', {STARTROW => '1001', STOPROW => '1003'}
      ROW COLUMN+CELL
      1001 column=info:name, timestamp=1717580289267, value=wangwu
      1002 column=info:name, timestamp=1717580320927, value=zhaoliu
      2 row(s)
      Took 0.0118 seconds
    • 删除数据 delete/deleteall

      删除数据的方式有两个:deletedeleteall

      • delete 表示删除一个版本的数据,即为 1Cell,不填写版本默认删除最新的一个版本。
      • deleteall 表示删除所有版本的数据,即为当前行当前列的多个 Cell。执行命令会标记数据为要删除,不会直接彻底删除,删除只在特定时期清理磁盘时进行。

      delete

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      hbase(main):001:0> put 'bigdata:student', '1001', 'info:name', 'zhangsan'
      Took 0.3910 seconds
      hbase(main):002:0> put 'bigdata:student', '1001', 'info:name', 'lisi'
      Took 0.2024 seconds
      hbase(main):003:0> put 'bigdata:student', '1001', 'info:name', 'wangwu'
      Took 0.1559 seconds

      hbase(main):004:0> scan 'bigdata:student'
      ROW COLUMN+CELL
      1001 column=info:name, timestamp=1717584831277, value=wangwu
      1002 column=info:name, timestamp=1717580320927, value=zhaoliu
      1003 column=info:age, timestamp=1717580366636, value=10
      1003 column=info:sex, timestamp=1717581149533, value=male
      3 row(s)
      Took 0.0083 seconds

      hbase(main):005:0> delete 'bigdata:student', '1001', 'info:name'
      Took 0.0055 seconds

      hbase(main):006:0> scan 'bigdata:student'
      ROW COLUMN+CELL
      1001 column=info:name, timestamp=1717584831277, value=lisi
      1002 column=info:name, timestamp=1717580320927, value=zhaoliu
      1003 column=info:age, timestamp=1717580366636, value=10
      1003 column=info:sex, timestamp=1717581149533, value=male
      3 row(s)
      Took 0.0087 seconds

      deleteall

      1
          
2.2.2 API操作

根据官方 API 介绍,HBase 的客户端连接由 ConnectionFactory 类来创建,用户使用完成之后需要手动关闭连接。同时连接是一个重量级的,推荐一个进程使用一个连接。对 HBase 的命令通过连接中的两个属性 AdminTable 来实现。其中 Admin 主要管理 HBase 的元数据,如创建、修改表格信息,也就是 DDL 操作;Table 主要用于表格的增加、删除数据,也就是 DML 操作。

  • 环境搭建

    使用 IDEA 创建 Maven 项目,并修改 pom.xml 文件,添加 HBase 所需要用到的依赖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<dependencies>
<dependency>
<groupId>org.apache.hbase</groupId>
<artifactId>hbase-client</artifactId>
<version>2.4.11</version>
<!-- 如果报错, 需要排除 javax.el 拓展 -->
<!-- 因为 2.4.11 对应的是一个测试版本的 javax.el 包 -->
<!-- 需要先排除这个包后再添加正式版的 javax.el 包 -->
<exclusions>
<exclusion>
<groupId>org.glassfish</groupId>
<artifactId>javax.el</artifactId>
</exclusion>
</exclusions>
</dependency>

<!-- 添加正式版的 javax.el 包 -->
<dependency>
<groupId>org.glassfish</groupId>
<artifactId>javax.el</artifactId>
<version>3.0.1-b06</version>
</dependency>
</dependencies>
  • 单线程使用连接

    下面展示了一种单线程使用连接的方式,实际开发中实际上很少这样做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package com.sdutcm;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.hbase.client.AsyncConnection;
import org.apache.hadoop.hbase.client.Connection;
import org.apache.hadoop.hbase.client.ConnectionFactory;

import java.io.IOException;
import java.util.concurrent.CompletableFuture;


public class HBaseConnection {
public static void main(String[] args) throws IOException {
// 1. 创建连接配置对象
Configuration conf = new Configuration();

// 2. 添加配置参数
conf.set("hbase.zookeeper.quorum", "bigdata"); // 这些配置都写在 hbase-site.xml 中

// 3. 创建连接
// 默认创建同步连接
Connection connection = ConnectionFactory.createConnection(conf);

// 也可以创建异步连接: 不推荐使用异步连接
CompletableFuture<AsyncConnection> asyncConnection = ConnectionFactory.createAsyncConnection(conf);

// 4. 使用连接
System.out.println(connection);

// 5. 关闭连接
connection.close();
}
}
  • 多线程使用连接

    实际开发中,因为 HBase 的连接是重量级的,所以我们在每个客户端中一般只创建一个(类似于单例模式)。所以我们对代码进行修改,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package com.sdutcm;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.hbase.client.AsyncConnection;
import org.apache.hadoop.hbase.client.Connection;
import org.apache.hadoop.hbase.client.ConnectionFactory;

import java.io.IOException;
import java.util.concurrent.CompletableFuture;


public class HBaseConnection {
// 声明一个静态属性
public static Connection connection = null;

static {
// 1. 创建连接配置对象: 当完成 resources 目录的配置后, 我们可以直接注释掉创建配置的部分
// 直接进行创建连接操作
// Configuration conf = new Configuration();

// 2. 添加配置参数
// 实际开发中, 不应该在代码中显式的写参数, 而是将参数写在 resources 下的配置文件中
// 将虚拟机的 hbase-site.xml 放到 resources 目录下
// conf.set("hbase.zookeeper.quorum", "bigdata"); // 这些配置都写在 hbase-site.xml 中

// 3. 创建连接
// 默认创建同步连接
try {
// 这里修改为无参构造
// connection = ConnectionFactory.createConnection(conf);
// 这里通过查看 ConnectionFactory.createConnection() -> 查看 create() -> 可以发现 HBase 官方文档添加了两个配置文件
// 分别为 hbase-default.xml 和 hbase-site.xml
// 所以我们可以直接复制虚拟机的 hbase-site.xml 添加到 resources 目录下, 并且将这里改为无参构造
// 无参则默认使用读取本地 hbase-site.xml 文件的方式添加参数
connection = ConnectionFactory.createConnection();
} catch (IOException e) {
e.printStackTrace();
}
}

// 关闭连接方式
public static void closeConnection() throws IOException {
// 判断连接是否为空
if (connection != null) {
connection.close();
}
}

public static void main(String[] args) throws IOException {
// 直接使用创建好的连接, 不要在 main 线程里面单独创建连接
System.out.println(HBaseConnection.connection);

// 使用完连接后需要关闭连接
HBaseConnection.closeConnection();
}
}
  • 获取 Admin
1
2
3
// 获取 Admin
// Admin 的连接式轻量级的, 不是线程安全的, 不推荐池化或者缓存这个连接
Admin admin = connection.getAdmin();
  • 创建命名空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package com.sdutcm;

import org.apache.hadoop.hbase.NamespaceDescriptor;
import org.apache.hadoop.hbase.client.Admin;
import org.apache.hadoop.hbase.client.Connection;

import java.io.IOException;

public class HBaseDDL {
// 声明一个静态属性, 这样我们可以在不同的类中, 调用到同一个对象
public static Connection connection = HBaseConnection.connection;

/**
* @brief 创建命名空间
* @param namespace 命名空间名称
*/
public static void createNamespace(String namespace) throws IOException {
// 1. 获取 Admin
// Admin 的连接式轻量级的, 不是线程安全的, 不推荐池化或者缓存这个连接
Admin admin = connection.getAdmin();

// 2. 调用方法创建命名空间
// 2.1 创建命名空间描述
NamespaceDescriptor.Builder builder = NamespaceDescriptor.create(namespace);

// 2.2 给命名空间添加需求
builder.addConfiguration("user", "sdutcm");

// 2.3 使用 builder 构造出对应的添加完参数的对象, 完成创建
admin.createNamespace(builder.build());

// 关闭 admin
admin.close();
}

public static void main(String[] args) throws IOException {
// 测试创建命名空间
createNamespace("sdutcm");

// 其他代码
System.out.println("其他代码");

// 关闭 HBase 连接
HBaseConnection.closeConnection();
}
}

​ 结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
hbase(main):001:0> list_namespace
NAMESPACE
default
hbase
sdutcm <<< 可以看到 sdutcm 已经被创建出来了
3 row(s)
Took 8.0120 seconds

hbase(main):002:0> describe_namespace "sdutcm"
DESCRIPTION
{NAME => 'sdutcm', user => 'sdutcm'} <<< 这里是我们添加的描述
Took 0.7576 seconds
=> 1
  • 多异常处理
1

  • 判断表格是否存在
  • 创建表格

📕 3. 底层原理

3.1 进程架构

3.1.1 Master架构
3.1.2 RegionServer架构

3.2 写流程

3.2.1 写入顺序
3.2.2 刷新机制

3.3 读流程

3.3.1 读取顺序
3.3.2 合并数据优化

3.4 文件合并

3.4.1 大合并
3.4.2 小合并

Region拆分

自定义预分区
系统拆分

🔧 企业开发

TSDB模式

基础表格模式

自定义API
整合框架
Phoenix 读写数据
Hive 分析数据

Better QT

[TOC]

🍞 Better QT

🍦 1. Qt 的一些常用技巧

1.1 快捷键

  • 快捷键 Ctrl + Tab 可以切换文件;
  • 快捷键 Alt + ENTER 弹出代码生成提示,可以快速提示错误修改方案,类似于 IDEA 的 Alt + ENTER
  • 快捷键 Alt + 鼠标 同时输入;
  • 快捷键 Ctrl + R 运行程序;
  • 快捷键 Ctrl + M 创建书签(Bookmark),或者直接在某行代码前右键添加书签;
  • 快捷键 Ctrl + ENTER 在当前行下方插入空行;
  • 快捷键 Ctrl + Shift + ENTER 在当前行下方插入空行;
  • 快捷键 Ctrl + I 代码对齐;
  • 快捷键 Ctrl + ; 格式化代码;
  • 快捷键 Shift + Delete 剪切当前行,可以当删除用;
  • 快捷键 Ctrl + Shift + R 局部变量统一修改;
  • 快捷键 Ctrl + Shift + V 复制历史;
  • 用键盘模拟鼠标操作:
    功能键 方向键 备注
    Ctrl Shift Alt 左/右 上/下 Home/End 方向键具有移动光标的作用
    × × × 字符 字符 行首/行尾 -
    × × 单词 滚动条 文件头/尾 -
    × 单词 移动 行首/行尾 Shift具有选中文本的作用
    × - 向上/下复制选中部分 - -
  • 快捷键 F1 查看帮助、文档
  • 快捷键 F2 快速到变量或者函数间切换
  • 快捷键 F4 快速在.cpp文件和.h文件间切换
  • 快捷键 Ctrl + Shift + U 查找所有使用该符号的地方
  • 快捷键 Ctrl + K 打开定位器
  • 快捷键 Ctrl + L 跳转到某一行
  • 快捷键 Ctrl + [Shift] + F 查找/替换当前文件[项目]当前选中的内容
  • 快捷键 [Shift] + F3 查找下[上]一个
  • 快捷键 Ctrl + B 编译工程
  • 快捷键 Ctrl + R 运行工程
  • 快捷键 F5 调试运行
  • 快捷键 Ctrl + Shift + F5 重启调试
  • 快捷键 F9 设置和取消断点
  • 快捷键 F10 单步跳过
  • 快捷键 F11 单步进入

1.2 Creator 片段

片段简单理解一下就是已经写好的一些模式化的代码,用户可以使用内置片段或者根据自己的需要自定义片段。

  1. 自带片段示例
    Qt Quick Part
  2. 自定义片段
    一个用户的自定义片段需要以下几个内容:
    $$片段 = 一级标题 + 二级标题 + 片段文本$$
    需要通过:编辑(Edit)→首选项(Preferences)→文本编辑器(Text Editor)→片段(Snippets)进行设置
    Qt Custom Snippets
    比如我要添加一个自定义片段 note,用来表示文件注释,可以选择 GroupC++,然后选择 Add,添加指定的内容:
    Add Custom Snippets

🍦 2. Qt 代码/文件解释

Qt的源代码和文件解释

2.1 Qt 代码

  • hellocosbrowser.h

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #ifndef HELLOCOSBROWSER_H
    #define HELLOCOSBROWSER_H

    #include <QWidget>
    #include <QMessageBox>

    QT_BEGIN_NAMESPACE
    namespace Ui { class HelloCOSBrowser; }
    QT_END_NAMESPACE

    class HelloCOSBrowser : public QWidget // QWidget 是所有应用程序窗口的基类
    {
    Q_OBJECT // Qt的宏, 支持 Qt 的特性, 如信号与槽、对象树、元对象等

    public:
    // 这里 HelloCOSBrowser 指定父窗口指针为 nullptr, 则它会作为一个独立的窗口进行展示, 否则则会作为父窗口的一个控件
    // 关于这个父窗口指针, 一个很典型的应用就是 微信
    // 当我们创建新窗口的时候, 如果不指定父窗口, 就会弹出一个独立的新窗口, 即电脑任务栏的图标会多出来一个
    // 如果指定了父窗口, 则不会创建一个独立的窗口, 即电脑任务栏处的图标不会增加
    HelloCOSBrowser(QWidget *parent = nullptr);
    ~HelloCOSBrowser();

    private slots:
    void showDialog();

    private:
    Ui::HelloCOSBrowser *ui;
    };
    #endif // HELLOCOSBROWSER_H

2.2 Qt 工程文件解释

文件列表

文件名称 描述
pro 文件 该文件是 Qt 的项目文件,qmake工具可以根据此文件生成 Makefile
pro.user 文件 该文件包含和用户相关的项目信息(用户不需要关注此文件)
ui 文件 Qt 的设计师界面文件
.cpp 文件 C++ 源文件
.h 文件 C++ 头文件

🍦 3. MOC编译器

MOC(Meta-Object Compiler)编译器
C++ 编译器本身不支持 Qt 的某些机制,Qt 希望对 C++ 代码进行自动扩展,这里就需要用到宏(例如:Q_Object)和继承。
此外为了方便用户使用,希望用户无感知,可以将这一操作直接集成到框架中。

3.1 Qt 编译过程

1
2
3
4
5
预编译 -> 编译 -> 汇编 -> 链接 -> 目标

+-------------------------+

拓展代码 -> MOC编译器 -> 新CPP代码

通过上述方式,实现 Qt 的某些特性。我们可以发现,当我们写完代码进行编译后,会产生一个 debug 文件夹,此时我们进入该文件夹,会看到一些元对象编译器编译的文件,如 moc_xxxx.cppmoc_xxx.h 等文件。

3.2 MOC 的使用方法

  1. MOC 编译工具由 Qt 框架自动调用
  2. 扫描 C++ 头文件,寻找 Q_OBJECT
  3. 生成拓展 C++ 代码,再进行预编译
  4. 程序员在使用时,需要继承 QObject 类或者是 QObject 子类,并且包含 Q_OBJECT 宏。

🍦 4. Qt应用程序开发

4.1 Qt Designer 设计师界面使用

Qt Designer
① Qt 控件编辑模式
② Qt 信号与槽编辑模式
③ Qt 伙伴关系编辑模式
④ Qt Tab 顺序编辑模式:可以设置按下 Tab 键的高亮顺序

4.2 Qt 核心——信号与槽

信号与槽的基本概念
Qt Signals and Slots

  • Qt 中的信号和槽是支持多对多的,即一个信号可以对应多个槽,一个槽可以由多个信号触发。
  • Qt 中的信号无需实现,可以由函数(普通函数或者槽函数)通过 emit 关键字发送信号传递参数。
4.2.1 Qt中如何定义信号
  1. 继承 QObject 类或其派生类,同时包含 Q_OBJECT
  2. 使用关键字 signals 声明函数信号函数,不需要具体实现信号函数
  3. 使用 emit 关键字发送信号
4.2.2 Qt中如何定义槽函数
  1. 必须包含 Q_OBJECT
  2. 使用关键字 [public/protected/private] slots 声明函数
  3. 需要具体实现声明的槽函数
4.2.3 Qt中如何连接信号与槽(三种写法)
  1. SIGNAL/SLOT 宏写法:
    QObject::connect(this, SIGNAL(...), this, SLOT(...));
  2. 函数指针写法:
    QObject::connect(this, &SignalFunction, this, &SlotFunction)
  3. lambda 表达式写法:
    QObject::connect(this, &SignalFunction, this, [=]() { qDebug() << "..."; })

三种写法的比较:

连接信号与槽 函数指针
编译 运行 编译 运行
参数类型 完全相同
隐式转换 向上 ×
向下 ×
不可以隐式转换 × × ×
参数个数 信号=槽
信号>槽
信号<槽 × × ×
  • 这样看来好像宏写法相对于函数指针的写法来说,可能会带来一些问题,因为有时候宏写法通过编译后,在运行阶段可能会出现一些问题;而函数指针写法可以在出现这一问题之前(编译阶段)提前发现这一问题,使得程序无法通过编译。
  • 但是事实上,宏写法还是存在一定的好处,当信号函数出现重载时,使用函数指针时,无法直接进行连接(会产生报错),只能使用类型转换来进行函数指针类型的转换,如static_cast<void QSpinBox::*)(int)>
  • 一般情况下,推荐使用函数指针方式连接信号与槽。
  • 当面对信号与槽函数有重载的情况时,推荐使用宏方式连接。
  • 对于短小的槽函数的调用且功能不被复用时,推荐使用 lambda 方式连接。
4.2.4 其他连接信号与槽的方式
  • 使用 Qt Designer 连接信号与槽
    Qt Designer Connect
  • 使用”转到槽”方式
  • 信号与槽自动绑定
    使用 void on_<对象名>_<信号名>(信号参数); 时可以不使用 connect 进行连接,但是当对象名、信号名或参数发生变化时,连接将会失效,且编译不会有错误提示。

4.3 Qt 窗口

4.3.1 窗口的类型

顶层窗口、次级窗口(父、子窗口)
Qt Windows
在该图中,①可以称为顶层窗口(父窗口),②可以称为次级窗口(子窗口)。窗口中的某些按钮、输入框…等就是控件。

4.3.2 设置窗口标志

在 Qt 中可以使用 setWindowFlags() 来设置窗口标志

  1. 设置窗口无标题栏
    Window With No Title

    1
    this->setWindowFlags(Qt::CustomizeWindowHint);
  2. 设置窗口无边框
    Window With No Frame

    1
    setWindowFlags(Qt::FramelessWindowHint);
  3. 设置窗口置顶

    1
    setWindowFlags(Qt::WindowStaysOnTopHint);

    如果按照上述方式依次设置窗口标志,我们会发现当设置第 $3$ 步时前面两步的操作都失效了,这是因为设置窗口置顶时,会覆盖前面的设置。我们可以使用“或”符连接这些标志,解决这一问题:

    1
    setWindowFlags(Qt::CustomizeWindowHint | Qt::FramelessWindowHint | Qt::WindowStaysOnTopHint);

4.4 窗口坐标系与几何布局

4.4.1 窗口的坐标系
Window Coordinate System
4.4.2 窗口的几何布局
Window Layout

4.5 添加图标

4.5.1 为窗口添加图标
  1. 准备图标文件
  2. 调用 setWindowIcon 方法
4.5.2 为应用程序添加图标(一般使用这种方式)
  1. 准备图标文件 logo.ico
  2. 修改 pro 工程文件 RC_ICONS = <Path>
  3. 通过此种方式修改图标,可执行程序 .exe 的图标会修改,且不需要额外单独设置窗口图标。

4.6 部署产品的三种方式

  1. 手动部署(不常用,比较繁琐)
    进入 .exe 文件所在的文件夹(debug目录),双击运行 .exe 文件,会提示缺少的文件(包括dll动态库、plugin插件等),然后找到对应的文件移动到 .exe 文件的同级目录下即可,如下:
    EXE File Dictionary
    如果配置了环境变量则大概率不会出现报错提示缺少库的问题,那么这种方式就会失效。

  2. 使用 windeployqt 部署
    ① 查找 windeployqt.exe 程序
    ② 将 windeployqt.exe 加入环境变量
    ③ 再命令行界面执行命令 windeployqt.exe <exe_file_dir> 完成操作
    WIN DEPLOY QT
    WIN DEPLOY QT
    WIN DEPLOY QT

  3. 使用creator 部署
    ① 项目导航窗口→运行→部署→添加自定义部署
    CREATOR DEPLOY
    CREATOR DEPLOY
    CREATOR DEPLOY
    ② 输入 windeployqt.exe 程序及对应的命令行参数
    CREATOR DEPLOY
    CREATOR DEPLOY
    ③ 执行部署命令
    CREATOR DEPLOY
    CREATOR DEPLOY OK

🍦 5. Qt 常用控件

官方文档:Qt 6.7

一个不错的 Qt 中文文档:Qt 中文文档 5.15.1 版本

5.1 QLabel 标签控件

QLabel 的本质其实就是显示数据。其可以显示文本数据、图片数据。

了解了这些我们再来看 QLabel 的一些常用属性:

属性 说明
text: QString 文本内容:纯文本
openExternalLinks:bool 文本内容:超链接
textFormat : Qt::TextFormat 文本内容:不同类型的文本,如富文本等
alignment: Qt::Alignment 文本格式:对齐方式
indent: int 文本格式:缩进
margin : int 文本格式:边距
wordWrap: bool 文本格式:换行
pixmap: QPixmap 图片内容:显示图片
hasSelectedText: const bool 方法:文本是否被选中
scaledContents: bool 方法:是否缩放内容
selectedText: const QString 方法:获取选中的内容
textInteractionFlags: Qt::TextInteractionFlags 方法:指定标签应如何与用户输入交互,若它显示文本

5.2 QLineEdit 单行输入框控件

QLineEdit 的本质是用于不确定的输入,如用户的手机号、用户的密码。这样就给了用户一定的自由,但是我们同时需要制定一系列的规则,以校验用户的输入。例如用户输入手机号,我们需要制定一个长度为 11 位的规则,并且输入字符中不包含字母等,以方便开发人员进行校验。当然我们也可以配合一些其他操作来优化用户体验,如:清空(如:快速清空内容)、提示(如:提示输入格式)、记忆(如:记忆之前的输入)等。

了解了这些我们可以看一下 QLineEdit 的一些常用属性(不完全,具体还是需要看文档):

属性 说明
clearButtonEnabled: bool 清空文本框内容
该属性保存行编辑不为空时是否显示清除按钮。
placeholderText: QString 占位符文本,可以用于提示输入内容。
inputMask: QString 掩码

IDEA 2022 搭建 Tomcat 环境

[TOC]

Tomcat 环境的搭建

参考教程

下载 Tomcat

Tomcat官网地址
Tomcat官网
在 Tomcat 官网中下载指定版本的 Tomcat,左侧 Download 处有相应版本,这里推荐 Tomcat 9 版本(因为Tomcat 10 在配置时会出现一定的问题)。
TomcatDownload
下载后解压到指定位置即可。

配置环境变量即可

配置 Tomcat 环境变量前一定要配置好 Java 的环境变量,尤其是JAVA_HOME,这里我一开始并没有配置 JAVA_HOME,我的环境变量是JAVA_HOME_180=xxx,这种方式Tomcat是找不到JAVA_HOME的,因此我又重新配置了JAVA_HOME
我的 JAVA_HOME 环境变量为:

1
JAVA_HOME=D:\JDK\jdk1.8.0_231

下面是 Tomcat 的环境变量配置:
新建 CATALINA_HOME 环境变量:

1
CATALINA_HOME=D:\tomcat\apache-tomcat-9.0.89

修改Path,在 Path 后添加(新建)如下环境变量:

1
2
3
%CATALINA_HOME%\lib
%CATALINA_HOME%\bin
%CATALINA_HOME%\lib\servlet-api.jar

验证是否配置成功

在命令行中,执行命令:startup.bat,若正常打印相关配置变量、且 Tomcat 进程被阻塞,即证明环境搭建成功。访问localhost:8080,出现以下界面即证明成功搭建。
TomcatSuccess
使用 shutdown.bat 命令即可使阻塞的 Tomcat 进程被关闭,推荐使用这种方式关闭 Tomcat。

可能会出现的问题

  1. 协议处理程序初始化失败:参考教程
    这个问题有可能是由于8080端口被占用了,在Windows中可以使用如下命令查看端口的占用情况:
    1
    netstat -aon|findstr "8080"
    如果确实被占用了,可以使用如下命令杀死端口号为 <PIDNUM> 的进程。
    1
    taskkill -PID <PIDNUM> -F
  2. 闪退
    可能原因是:环境变量配置不正确,仔细检查环境变量的配置。
  3. 乱码
    问题描述:打开startup.bat后汉字乱码
    解决方法:在.\apache-tomcat-9.0.43\conf下打开logging.properties文件
    java.util.logging.ConsoleHandler.encoding = UTF-8替换为java.util.logging.ConsoleHandler.encoding = GBK

社区版 IDEA 如何配置 Tomcat

CSDN 上大多数教程使用 Maven 创建 Tomcat 项目,但是这种方法实在是过于麻烦,社区版和专业版又有些不同,找不到很多东西。

如何配置 IDEA 2022 社区版中的 Tomcat

  1. 安装插件
    在 File → Settings → Plugin 中安装插件,搜索 Tomcat,安装插件。
    SmartTomcat
  2. 配置Tomcat路径
    安装插件后,在 File → Settings → Plugin → Tomcat Server
    添加配置如下:
    SmartTomcatConfig
  3. 完成

BELKA_2024

[TOC]

Leash Bio - Predict New Medicines with BELKA

BELKA 预测新药

Predict small molecule-protein interactions using the Big Encoded Library for Chemical Assessment (BELKA)

使用化学评估大编码库(BELKA)预测小分子蛋白质相互作用

Overview

In this competition, you’ll develop machine learning (ML) models to predict the binding affinity of small molecules to specific protein targets – a critical step in drug development for the pharmaceutical industry that would pave the way for more accurate drug discovery. You’ll help predict which drug-like small molecules (chemicals) will bind to three possible protein targets.

在这场比赛中,你将开发机器学习(ML)模型来预测小分子与特定蛋白质靶标(目标蛋白)的结合亲和力——这是制药行业药物开发的关键一步,将为更准确的药物发现铺平道路。你将帮助预测哪种药物样的小分子(化学物质)将与三种可能的蛋白质靶点结合。

Description

Small molecule drugs are chemicals that interact with cellular protein machinery and affect the functions of this machinery in some way. Often, drugs are meant to inhibit the activity of single protein targets, and those targets are thought to be involved in a disease process. A classic approach to identify such candidate molecules is to physically make them, one by one, and then expose them to the protein target of interest and test if the two interact. This can be a fairly laborious and time-intensive process.

小分子药物是与细胞蛋白质机制相互作用并以某种方式影响该机制功能的化学物质。通常,药物旨在抑制单个蛋白质靶标的活性,而这些靶标被认为与疾病过程有关。识别这类候选分子的一种经典方法是一个接一个地进行物理制造,然后将其暴露于感兴趣的蛋白质靶点,并测试两者是否相互作用。这可能是一个相当费力和耗时的过程。

The US Food and Drug Administration (FDA) has approved roughly 2,000 novel molecular entities in its entire history. However, the number of chemicals in druglike space has been estimated to be 10^60, a space far too big to physically search. There are likely effective treatments for human ailments hiding in that chemical space, and better methods to find such treatments are desirable to us all.

美国食品药品监督管理局(FDA)已经批准了大约2000种新型分子实体在其整个历史. 然而,类药物领域的化学物质数量估计为$10^60$,这个空间太大了,无法进行物理搜索。在这个化学空间里,可能有有效的治疗人类疾病的方法,而找到更好的治疗方法对我们所有人来说都是可取的。

To evaluate potential search methods in small molecule chemistry, competition host Leash Biosciences physically tested some 133M small molecules for their ability to interact with one of three protein targets using DNA-encoded chemical library (DEL) technology. This dataset, the Big Encoded Library for Chemical Assessment (BELKA), provides an excellent opportunity to develop predictive models that may advance drug discovery.

为了评估小分子化学中潜在的搜索方法,比赛主办方Leash Biosciences使用DNA编码化学文库(DEL)技术对约133M个小分子进行了物理测试,以确定它们与三个蛋白质靶标之一相互作用的能力。该数据集,即化学评估大编码库(BELKA),为开发可能促进药物发现的预测模型提供了极好的机会。

Datasets of this size are rare and restricted to large pharmaceutical companies. The current best-curated public dataset of this kind is perhaps bindingdb, which, at 2.8M binding measurements, is much smaller than BELKA.

这种规模的数据集非常罕见,仅限于大型制药公司。目前这类最好的公共数据集可能是bindingdb,在2.8M的结合测量值下,比BELKA小得多。

This competition aims to revolutionize small molecule binding prediction by harnessing ML techniques. Recent advances in ML approaches suggest it might be possible to search chemical space by inference using well-trained computational models rather than running laboratory experiments. Similar progress in other fields suggest using ML to search across vast spaces could be a generalizable approach applicable to many domains. We hope that by providing BELKA we will democratize aspects of computational drug discovery and assist the community in finding new lifesaving medicines.

这项竞赛旨在通过利用ML技术彻底改变小分子结合预测。ML方法的最新进展表明,使用训练有素的计算模型而不是进行实验室 实验,通过推理搜索化学空间是可能的。其他 领域的类似进展表明,使用ML在广阔的空间中搜索可能是一种适用于许多领域的通用方法。我们希望通过提供BELKA,我们将使计算药物发现的各个方面民主化,并帮助社区寻找新的救命药物。

Here, you’ll build predictive models to estimate the binding affinity of unknown chemical compounds to specified protein targets. You may use the training data provided; alternatively, there are a number of methods to make small molecule binding predictions without relying on empirical binding data (e.g. DiffDock, and this contest was designed to allow for such submissions).

在这里,你将建立预测模型来估计未知化合物与特定蛋白质靶标的结合亲和力。您可以使用提供的培训数据;或者,有许多方法可以在不依赖经验结合数据的情况下进行小分子结合预测(例如DiffDock,而本次竞赛旨在允许此类提交)。

Your work will contribute to advances in small molecule chemistry used to accelerate drug discovery.

你的工作将有助于促进用于加速药物发现的小分子化学的进步。

Evaluation

This metric for this competition is the average precision calculated for each (protein, split group) and then averaged for the final score. Please see this forum post for important details.

这项比赛的指标是为每个(蛋白质、分组)计算的平均精度,然后为最终得分取平均值。请参阅此论坛帖子了解重要细节。

Here’s the code for the implementation.

这是代码以供实施。

Submission File

For each id in the test set, you must predict a probability for the binary target binds target. The file should contain a header and have the following format:

对于测试集中的每个id您必须预测二进制目标“绑定”目标的概率。该文件应包含一个标头,并具有以下格式:

1
2
3
4
5
id,binds
295246830,0.5
295246831,0.5
295246832,0.5
etc.

Timeline

  • April 4, 2024 - Start Date.
  • July 1, 2024 - Entry Deadline. You must accept the competition rules before this date in order to compete.
  • July 1, 2024 - Team Merger Deadline. This is the last day participants may join or merge teams.
  • July 8, 2024 - Final Submission Deadline.

All deadlines are at 11:59 PM UTC on the corresponding day unless otherwise noted. The competition organizers reserve the right to update the contest timeline if they deem it necessary.

Prizes

  • First Prize: $12,000
  • Second Prize: $10,000
  • Third Prize: $10,000
  • Fourth Prize: $8,000
  • Fifth Prize: $5,000
  • Top Student Group: $5,000 to the highest performing student team. A team would be considered a student team if majority members (e.g. at least 3 out of a 5 member team) are students enrolled in a high school or university degree. In the case of an even number of members, half of them must be students.

Competition Host

Leash Biosciences is a discovery-stage biotechnology company that seeks to improve medicinal chemistry with machine learning approaches and massive data collection. Leash is comprised of wet lab scientists and dry lab scientists in equal numbers, and is proudly headquartered in Salt Lake City, Utah, USA.

Additional Details

Chemical Representations

One of the goals of this competition is to explore and compare many different ways of representing molecules. Small molecules have been [represented](https://pubs.acs.org/doi/10.1021/acsinfocus.7e7006?ref=infocus%2FAI_& Machine Learning) with SMILES, graphs, 3D structures, and more, including more esoteric methods such as spherical convolutional neural nets. We encourage competitors to explore not only different methods of making predictions but also to try different ways of representing the molecules.

We provide the molecules in SMILES format.

这场比赛的目标之一是探索和比较许多不同的分子表现方式。小分子已经用SMILES、图形、3D结构等表示,包括更深奥的方法,如球形卷积神经网络。我们鼓励竞争对手不仅探索不同的预测方法,还尝试不同的分子表示方法。

我们提供SMILES格式的分子。

SMILES

SMILES is a concise string notation used to represent the structure of chemical molecules. It encodes the molecular graph, including atoms, bonds, connectivity, and stereochemistry as a linear sequence of characters, by traversing the molecule graph. SMILES is widely used in machine learning applications for chemistry, such as molecular property prediction, drug discovery, and materials design, as it provides a standardized and machine-readable format for representing and manipulating chemical structures.

The SMILES in this dataset should be sufficient to be translated into any other chemical representation format that you want to try. A simple way to perform some of these translations is with RDKit.

SMILES是一种简明的字符串表示法,用于表示化学分子的结构。它通过遍历分子图,将分子图(包括原子、键、连接性和立体化学)编码为线性字符序列。SMILES广泛用于化学的机器学习应用,如分子性质预测、药物发现和材料设计,因为它为表示和操纵化学结构提供了标准化和机器可读的格式。
该数据集中的SMILES应该足以转换为您想要尝试的任何其他化学表示格式。执行其中一些翻译的一种简单方法是使用RDKit.

Details about the experiments

DELs are libraries of small molecules with unique DNA barcodes covalently attached

Traditional high-throughput screening requires keeping individual small molecules in separate, identifiable tubes and demands a lot of liquid handling to test each one of those against the protein target of interest in a separate reaction. The logistical overhead of these efforts tends to restrict screening collections, called libraries, to 50K-5M small molecules. A scalable solution to this problem, DNA-encoded chemical libraries, was described in 2009. As DNA sequencing got cheaper and cheaper, it became clear that DNA itself could be used as a label to identify, and deconvolute, collections of molecules in a complex mixture. DELs leverage this DNA sequencing technology.

These barcoded small molecules are in a pool (many in a single tube, rather than one tube per small molecule) and are exposed to the protein target of interest in solution. The protein target of interest is then rinsed to remove small molecules in the DEL that don’t bind the target, and the remaining binders are collected and their DNA sequenced.

DEL是共价连接有独特DNA条形码的小分子库
传统高通量筛选需要将单个小分子保持在单独的、可识别的管中,并且需要大量的液体处理来在单独的反应中针对感兴趣的蛋白质靶标测试其中的每一个。这些工作的后勤开销往往将筛选收藏(称为文库)限制在5000万至500万个小分子以内。这个问题的一个可扩展的解决方案,DNA编码的化学文库,在2009年描述. 随着DNA测序变得越来越便宜,很明显,DNA本身可以用作标签来识别和消除复杂混合物中分子的聚集。DELs这种DNA测序技术。
这些条形码小分子在一个池中(许多在单管中,而不是每个小分子一管),并暴露于溶液中感兴趣的蛋白质靶标。然后冲洗感兴趣的蛋白质靶标,以去除DEL中不与靶标结合的小分子,收集剩余的结合物并对其DNA进行测序。

DELs are manufactured by combining different building blocks

An intuitive way to think about DELs is to imagine a Mickey Mouse head as an example of a small molecule in the DEL. We attach the DNA barcode to Mickey’s chin. Mickey’s left ear is connected by a zipper; Mickey’s right ear is connected by velcro. These attachment points of zippers and velcro are analogies to different chemical reactions one might use to construct the DEL.

We could purchase ten different Mickey Mouse faces, ten different zipper ears, and ten different velcro ears, and use them to construct our small molecule library. By creating every combination of these three, we’ll have 1,000 small molecules, but we only needed thirty building blocks (faces and ears) to make them. This combinatorial approach is what allows DELs to have so many members: the library in this competition is composed of 133M small molecules. The 133M small molecule library used here, AMA014, was provided by AlphaMa. It has a triazine core and superficially resembles the DELs described here.

DEL是通过组合不同的构建块来制造的
一个思考DEL的直观方法是想象一个米老鼠的头作为DEL中一个小分子的例子。我们把DNA条形码贴在米奇的下巴上。米奇的左耳由拉链连接;米奇的右耳是用尼龙搭扣连接的。拉链和尼龙搭扣的这些连接点类似于可能用于构建DEL的不同化学反应。
我们可以购买十个不同的米老鼠脸、十个不同拉链耳朵和十个不同尼龙搭扣耳朵,并用它们来构建我们的小分子库。通过创建这三者的每一个组合,我们将拥有1000个小分子,但我们只需要30个构建块(脸和耳朵)就可以制造它们。这种组合方法使DEL能够拥有如此多的成员:这场竞争中的文库由133M个小分子组成。这里使用的133M小分子文库AMA014由AlphaMa提供。它有一个三嗪核心,表面上类似于此处描述的DEL。

Acknowledgements

Leash Biosciences is grateful for the generous cosponsorship of Top Harvest Capital and AlphaMa.

Citation

Andrew Blevins, Ian K Quigley, Brayden J Halverson, Nate Wilkinson, Rebecca S Levin, Agastya Pulapaka, Walter Reade, Addison Howard. (2024). Leash Bio - Predict New Medicines with BELKA. Kaggle. https://kaggle.com/competitions/leash-BELKA


Dataset Description

Overview

The examples in the competition dataset are represented by a binary classification of whether a given small molecule is a binder or not to one of three protein targets. The data were collected using DNA-encoded chemical library (DEL) technology.

比赛数据集中的例子由给定小分子是否与三个蛋白质靶标之一结合的二元分类表示。使用DNA编码化学文库(DEL)技术收集数据。

We represent chemistry with SMILES (Simplified Molecular-Input Line-Entry System) and the labels as binary binding classifications, one per protein target of three targets.

我们用SMILES(简化分子输入 行输入系统)和二元绑定分类来表示化学,三个靶标中的每个蛋白质靶标都有一个。

Files

[train/test].[csv/parquet] - The train or test data, available in both the csv and parquet formats.

  • id - A unique example_id that we use to identify the molecule-binding target pair.
  • buildingblock1_smiles - The structure, in SMILES, of the first building block
  • buildingblock2_smiles - The structure, in SMILES, of the second building block
  • buildingblock3_smiles - The structure, in SMILES, of the third building block
  • molecule_smiles - The structure of the fully assembled molecule, in SMILES. This includes the three building blocks and the triazine core. Note we use a [Dy] as the stand-in for the DNA linker.
  • protein_name - The protein target name
  • binds - The target column. A binary class label of whether the molecule binds to the protein. Not available for the test set.

sample_submission.csv - A sample submission file in the correct format

[train/test].[csv/parquet] - 训练或测试数据,csv和parquet格式均可。

  • id - 我们用来识别分子结合靶标对的唯一示例_id。
  • buildingblock1_smiles - 第一个构建块的结构,以SMILES表示
  • buildingblock2_smiles - 第二个构建块的结构,以SMILES表示
  • buildingblock3_smiles - 第三个构建块的结构,以SMILES表示
  • molecule_smiles - 完全组装的分子的结构,以SMILES表示。这包括三个构建块和三嗪核心。请注意,我们使用[Dy]作为DNA连接子的替代。
  • protein_name - 蛋白质靶标名称
  • binds - 目标列。分子是否与蛋白质结合的二进制类标签。不适用于测试集。

Competition data

All data were generated in-house at Leash Biosciences. We are providing roughly 98M training examples per protein, 200K validation examples per protein, and 360K test molecules per protein. To test generalizability, the test set contains building blocks that are not in the training set. These datasets are very imbalanced: roughly 0.5% of examples are classified as binders; we used 3 rounds of selection in triplicate to identify binders experimentally. Following the competition, Leash will make all the data available for future use (3 targets × 3 rounds of selection × 3 replicates × 133M molecules, or 3.6B measurements).

所有数据均由Leash Biosciences公司内部生成。我们为每种蛋白质提供了大约 98M 个训练实例,为每种蛋白提供了 200K 个验证实例,为每个蛋白质提供了 360K 个测试分子。为了测试可推广性,测试集包含不在训练集中的构建块。这些数据集非常不平衡:大约0.5%的示例被归类为绑定;我们使用了三轮一式三份的选择来实验鉴定粘合剂。比赛结束后,Leash将提供所有数据供未来使用(3个靶标×3轮选择×3个重复×3.33M个分子,或3.6B测量值)。

Targets

Proteins are encoded in the genome, and names of the genes encoding those proteins are typically bestowed by their discoverers and regulated by the Hugo Gene Nomenclature Committee. The protein products of these genes can sometimes have different names, often due to the history of their discovery.

We screened three protein targets for this competition.

蛋白质在基因组中编码,编码这些蛋白质的基因的名称通常由其发现者命名,并由雨果基因命名委员会监管。这些基因的蛋白质产物有时可能有不同的名称,通常是由于它们的发现历史。
我们为这次比赛筛选了三个蛋白质靶点。

EPHX2 (sEH)

The first target, epoxide hydrolase 2, is encoded by the EPHX2 genetic locus, and its protein product is commonly named “soluble epoxide hydrolase”, or abbreviated to sEH. Hydrolases are enzymes that catalyze certain chemical reactions, and EPHX2/sEH also hydrolyzes certain phosphate groups. EPHX2/sEH is a potential drug target for high blood pressure and diabetes progression, and small molecules inhibiting EPHX2/sEH from earlier DEL efforts made it to clinical trials.

EPHX2/sEH was also screened with DELs, and hits predicted with ML approaches, in a recent study but the screening data were not published. We included EPHX2/sEH to allow contestants an external gut check for model performance by comparing to these previously-published results.

We screened EPHX2/sEH purchased from Cayman Chemical, a life sciences commercial vendor. For those contestants wishing to incorporate protein structural information in their submissions, the amino sequence is positions 2-555 from UniProt entry P34913, the crystal structure can be found in PDB entry 3i28, and predicted structure can be found in AlphaFold2 entry 34913. Additional EPHX2/sEH crystal structures with ligands bound can be found in PDB.

第一个靶标环氧化物水解酶2由EPHX2基因座编码,其蛋白产物通常被命名为“可溶性环氧化物水解酶”,或缩写为sEH。水解酶是催化某些化学反应的酶,EPHX2/sEH也水解某些磷酸基团。EPHX2/sEH是高血压和糖尿病进展的潜在药物靶点,早期DEL研究中抑制EPHX2/s EH的小分子已进入临床试验.
EPHX2/sEH也用DEL进行了筛选,并用ML方法预测了命中率(https://blog.research.google/2020/06/unlocking-chemome-with-dna-encoded.html学习https://pubs.acs.org/doi/10.1021/acs.jmedchem.0c00452)但筛选数据没有公布。我们纳入了EPHX2/sEH,通过与之前公布的结果进行比较,让参赛者能够对模型性能进行外部检查。
我们筛选了EPHX2/sEH购自开曼化学. 在PDB中可以发现具有结合配体的额外的EPHX2/sEH晶体结构。

BRD4

The second target, bromodomain 4, is encoded by the BRD4 locus and its protein product is also named BRD4. Bromodomains bind to protein spools in the nucleus that DNA wraps around (called histones) and affect the likelihood that the DNA nearby is going to be transcribed, producing new gene products. Bromodomains play roles in cancer progression and a number of drugs have been discovered to inhibit their activities.

BRD4 has been screened with DEL approaches previously but the screening data were not published. We included BRD4 to allow contestants to evaluate candidate molecules for oncology indications.

We screened BRD4 purchased from Active Motif, a life sciences commercial vendor. For those contestants wishing to incorporate protein structural information in their submissions, the amino acid sequence is positions 44-460 from UniProt entry O60885-1, the crystal structure (for a single domain) can be found in PDB entry 7USK and predicted structure can be found in AlphaFold2 entry O60885. Additional BRD4 crystal structures with ligands bound can be found in PDB.

ALB (HSA)

The third target, serum albumin, is encoded by the ALB locus and its protein product is also named ALB. The protein product is sometimes abbreviated as HSA, for “human serum albumin”. ALB, the most common protein in the blood, is used to drive osmotic pressure (to bring fluid back from tissues into blood vessels) and to transport many ligands, hormones, fatty acids, and more.

Albumin, being the most abundant protein in the blood, often plays a role in absorbing candidate drugs in the body and sequestering them from their target tissues. Adjusting candidate drugs to bind less to albumin and other blood proteins is a strategy to help these candidate drugs be more effective.

ALB has been screened with DEL approaches previously but the screening data were not published. We included ALB to allow contestants to build models that might have a larger impact on drug discovery across many disease types. The ability to predict ALB binding well would allow drug developers to improve their candidate small molecule therapies much more quickly than physically manufacturing many variants and testing them against ALB empirically in an iterative process.

We screened ALB purchased from Active Motif. For those contestants wishing to incorporate protein structural information in their submissions, the amino acid sequence is positions 25 to 609 from UniProt entry P02768, the crystal structure can be found in PDB entry 1AO6, and predicted structure can be found in AlphaFold2 entry P02768. Additional ALB crystal structures with ligands bound can be found in PDB.

Good luck!

Tree

树(Tree)

[TOC]

树的基本概念

树是一种非常重要的非线性数据结构,树的一个节点可能会生出多个分支。一般而言,一棵树会包含一个根节点,向下延伸出若干子节点,每个末端的节点被称为叶子节点。

有根树

有根树存在一个根节点Root,如下:

对于图中概念的一些补充:

  • 节点拥有的子节点个数叫做节点的
  • 具有相同深度的节点处于同一层,方便表示。
  • 节点和节点之间的线叫做
  • 路径:指从树上一点到另外一点所经过的不重合的点和边的集合,题目中有时会单指点或边的集合。
  • 一颗 $n$ 个节点的树,一定有 $n-1$ 条边

无根树


二叉树

二叉树是一种特殊的树

  • 所有节点的度都不超过2的树称为二叉树。
  • 因为每个二叉树的节点最多只会有两个子结点,它的两个子节点一般会被称为左、右儿子,两棵子树一般会被称为左、右子树。
  • 左、右儿子甚至根节点本身都有可能缺失(一个节点都没有可以称为空二叉树)。

满二叉树和完全二叉树

二叉树也有两个比较特殊的类型:满二叉树和完全二叉树

  • 满二叉树:所有层的节点全满。
    • 满二叉树的一些规律
      • 第 $n$ 层的节点个数为 $2^{n-1}$
      • 深度为 $n$ 的满二叉树节点数为 $2^0 + 2^1 + 2^2 + \dots + 2^{n-1}= 2^n-1$
  • 完全二叉树:除了最后一层以外,其他层的节点个数全满,而且最后一层的节点从左到右排满直到最后一个节点。
    • 完全二叉树的一些规律
      • 完全二叉树的节点个数不会少于 $(2^{n-1}-1)+1 = 2^{n-1}$
      • 完全二叉树的节点个数不会多于 $2^{n} - 1$
      • 一棵完全二叉树,设当前节点为 $t$,其父节点为 $t/2$,其左儿子为 $2t$,其右儿子为 $2t+1$,借助该规律,我们可以将完全二叉树使用数组进行存储。
  • 完全二叉树的存储
    • 完全二叉树由于它的特性,可以简单用数组来模拟其结构
    • 一般会以数组$[1]$位置为根节点建立二叉树
    • 数组$[t]$位置的左儿子和右儿子对应的位置分别为$[2t]$和$[2t+1]$,父节点的位置为$[t/2]$。
    • 堆、线段树等数据结构的建立也会参考这个方式

完全二叉树的建立(使用数组),使用这种方法建立非完全二叉树,会导致空间的浪费:

1
2
3
4
5
6
7
8
void build(int t) {
// 添加数据
UpdateData(t);

// 如果子节点存在
Build(2 * t);
Build(2 * t + 1);
}

为了解决这个问题,我们可以使用其他方法来完成一般二叉树的存储,可以用数组下标模拟节点编号,用多个数组来记录节点信息。为了方便,我们也可以使用结构体来存储这些信息:

1
2
3
4
5
// 使用结构体来实现上述操作
struct TreeNode {
int value;
int l, r, fa;
}a[100010];

当然,作为一种树形结构,使用指针显然是更合适的方法:

1
2
3
4
5
6
7
8
9
// 使用指针来实现上述操作
struct TreeNode {
int value;
TreeNode* l;
TreeNode* r;
TreeNode* fa;
};

TreeNode* root;

使用指针的一些操作:

  • 新建节点:
    1
    2
    3
    4
    5
    6
    7
    struct TreeNode {
    int value;
    TreeNode *l, *r, *fa; // 初始为 NULL
    TreeNode(int x){ value = x; }
    };

    TreeNode* treeNode = new TreeNode(x);
  • 根节点初始化:
    1
    2
    TreeNode* root;
    root = new TreeNode(v);
  • 插入节点:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void Insert(TreeNode* fa, TreeNode* p, int flag){
    // flag = 0 插入到左边
    // flag = 1 插入到右边
    if (!flag)
    fa->l = p;
    else
    fa->r = p;
    p->fa = fa;
    }
    TreeNode* treeNode = new TreeNode(v);
    Insert(fa, treeNode, flag);
  • 删除节点
    1
    // 删除节点

二叉树的遍历

二叉树的遍历可分为先序遍历、中序遍历和后序遍历,这三种方式以访问根节点的时间来区分。
先序遍历(Degree-Left-Right, DLR):根→左→右
中序遍历(Left-Degree-Right, LDR):左→根→右
先序遍历(Left-Right-Degree, LRD):左→右→根

在该图中,先序遍历的结果为 1 2 4 5 3 6 7,先序遍历代码如下:

1
2
3
4
5
6
7
void preOrder(TreeNode* treeNode) {
cout << p->value << endl;
if(treeNode->l) preOrder(treeNode->l);
if(treeNode->r) preOrder(treeNode->r);
}

preOrder(root);

在该图中,中序遍历的结果为 4 2 5 1 6 3 7,中序遍历代码如下:

1
2
3
4
5
6
7
void inOrder(TreeNode* treeNode) {
if(treeNode->l) inOrder(treeNode->l);
cout << p->value << endl;
if(treeNode->r) inOrder(treeNode->r);
}

inOrder(root);

在该图中,后序遍历的结果为 4 5 2 6 7 3 1,后序遍历代码如下:

1
2
3
4
5
6
7
void postOrder(TreeNode* treeNode) {
if(treeNode->l) postOrder(treeNode->l);
if(treeNode->r) postOrder(treeNode->r);
cout << p->value << endl;
}

postOrder(root);

除了上述的几种遍历方式,还有层级遍历(BFS)方式对树进行遍历。层级遍历是借助队列(Queue)来实现的,其过程可以描述如下:

层级遍历的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeNode* q[N];
void bfs(TreeNode* root) {
int front = 1, rear = 1;
q[1] = root;
while (front <= rear) {
TreeNode* p = q[front]; // 选取队列中最前面的节点
front++;
cout << p->value <<endl;
if(p->l) q[++rear] = p->l;
if(p->r) q[++rear] = p->r;
}
}

bfs(root);

计算节点的深度

我们可以在遍历树的时候同时进行节点深度的记录,简单来讲就是:
$$depth_{儿子} = depth_{父亲} + 1$$

有根树(Tree)

这里不再是二叉树这种特殊的树,而是一般意义的树。

树的存储方式

  • vector/链表
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // vector 方式
    vector<int> nodes[N + 1];
    int n, father[N + 1];

    // 在 x 和 y之间构建一条边
    void addEdge(int x, int y) {
    nodes[x].push_back(y);
    }

    // 遍历 x 的所有儿子
    int l = nodes[x].size();
    for (int i = 0; i < l; i++) {
    nodes[x][i];
    }

    for (auto i: nodes[x]) {
    ...
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 链表方式
    struct Node {
    int where;
    Node *next;
    } *head[N + 1], a[M];

    int n, father[N + 1], l = 0;

    void addEdge(int x, int y) {
    a[++i].where = y;
    a[l].next = head[x];
    head[x] = &a[l];
    }

    // 遍历 x 的所有儿子
    for (Node* p = head[x]; p; p->next) {
    p->where;
    }

有根树遍历

遍历一棵树一般有 DFS 和 BFS 两种方式。
DFS:深度优先搜索,从一个节点开始,选择一条路径并走到底,并通过回溯来访问所有节点。
BFS:广度优先搜索,也称层级顺序探索,从一个节点开始,遍历该节点的所有子节点,或称按照深度从小到大的顺序依次遍历所有点。

  • 有根树的DFS序
    有根树的 DFS 序是指,从根节点开始的深度优先搜索过程中,依次记录的点所生成的序列。
    对于上图,所生成的 DFS 序即为 ABCDEFGHIJKLMN。当然这个只是其中一种 DFS 序,因为 A 可以走向 B,也可以走向 E,当然也可以走向 F。不同的走向会有不同的 DFS 序。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    vector<int> dfn;      // 用于存储 DFS 序, 常用 DFN 表示 DFS 序
    // dfn 中的元素即为 DFS 序

    void dfs(int x) {
    dfn.push_back(x);
    // for x的所有儿子y { dfs(y); }
    //
    for (Node* p = x; p; p->next){ dfs(p->next) }
    }

    dfs(root);
  • 有根树的BFS序
    有根树的 BFS 序是指,从根节点开始的广度优先搜索过程中,依次记录的点所生成的序列。
    对于上图,所生成的 BFS 序即为 ABENCDFMGJHIKL。当然这个只是其中一种 BFS 序,因为同一深度可能会有不同的遍历顺序,如深度为 $2$ 时,BENBNEEBN、…都是可能出现的顺序,不同的顺序会有不同的 BFS 序。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void bfs(int root) {
    // 将 root 加入队列 q;
    q.push(root);

    // 遍历队列 q
    while(队列 q 非空) {
    x = q.top(); // 取队首元素
    q.pop(); // x 出队
    for x的所有儿子y {
    y 入队;
    }
    }
    }

无根树(Unrooted Tree)

无根树即没有固定根结点的树,树中的节点只有相邻关系而没有父子关系。无根树有几种等价的形式化定义(建议搭配图论一起学习):

  • 有 $n$ 个结点, $n−1$ 条边的连通无向图
  • 无向无环的连通图
  • 任意两个结点之间有且仅有一条简单路径的无向图
  • 任何边均为桥的连通图
  • 没有圈,且在任意不同两点间添加一条边之后所得图含唯一的一个圈的图

如下图所示,即一棵无根树:

无根树中的任意一个节点可以被指定为根,变成一棵有根树。

无根树的遍历

遍历一棵无根树一般也有 DFS 和 BFS 两种方式。
遍历无根树时,可以从任意一个节点开始,以类似有根树的方式,遍历整棵树。唯一的区别是在进入一个新节点时,需要记录这个节点的来源节点,在遍历新节点的相邻节点时,避免重复访问来源节点即可。

  • 无根树的 DFS
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void dfs(int from, int x) {
    for x的所有响铃节点y {
    if (y != from) {
    dfs(x, y);
    }
    }
    }

    dfs(-1, x);
  • 无根树的 BFS
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void bfs(int x) {
    // 将 x 加入队列 q,x 的来源为空
    while (队列 q 非空) {
    x = q.top();
    from = x的来源节点;
    q.pop;
    for x的所有相邻节点 y {
    if (y != from) {
    y 入队;
    记录 y 的来源节点为 x;
    }
    }
    }
    }

    bfs(x);

树的直径

  • 树的直径是指树上任意两个节点之间最长(路径的长度一般指的是路径经过的边的数量)的路径。
  • 一棵树可以存在很多条直径,他们的长度相等。
  • 树的直径的中间节点被称为树的中心(图中C节点),如果直径上有偶数个节点,那么中间的两个节点都可以是树的中心。
  • 树的中心到其它点的最长路径最短。

Heap

堆(Heap)

[TOC]

堆的基本概念

二叉堆的基本概念和基本性质

堆是一种树形结构,有二叉树就有二叉堆。

  • 二叉堆总是一棵完全二叉树
  • 堆中某个结点的值总是不大于或不小于其父结点的值
  • 根节点的值为整个堆中的最小/最大值。
    • 父节点中的值大于等于两个子节点中的值,根节点的值最大的堆称为大根堆
    • 父节点中的值小于等于两个子节点中的值,根节点的值最小的堆称为小根堆
  • 我们可以在堆中插入和删除元素,然后通过调整元素的位置来维护堆的性质。

堆的操作

  • 堆的初始化
    在建立堆之前,需要初始化一些东西:
    • 一个空数组,用于存储堆中的元素
    • 一个记录堆中元素个数的变量
      1
      2
      3
      const int MAXSIZE = 10000;
      int len = 0;
      int heap[MAXSIZE + 1];
  • 堆中元素的插入
    堆在插入时,需要首先将插入元素放在数组末尾,然后插入元素不断的和其父节点比较,直到位置合适。下面是对小根堆插入过程的模拟:

    小根堆插入的代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void insert(int x) {
    heap[++len] = x;
    up(len);
    }

    void up(int k) {
    while(k > 1 && heap[k] < heap[k/2]) {
    swap(heap[k], heap[k/2]);
    k /= 2;
    }
    }

    int main(void) {
    insert(x);
    return 0;
    }
    大根堆和小根堆插入元素的方式基本相同,只需要改变大于/小于符号,插入操作的时间复杂度为 $O(log;n)$
  • 堆顶元素的删除
    堆最常用的功能就是维护最小/最大值。在使用小根堆时,我们经常会求得最小的数字,然后让它出堆,这时就要从堆中删除堆顶数据。
    这时除了堆顶为空,它的左子树堆和右子树堆仍满堆结构。为了操作简单,一般选择将堆尾部元素放到堆顶,然后将其逐步下移的方式,下移时,如进行交换操作,交换的是该节点左右儿子中较小的一个与该节点。
    下图模拟小根堆删除堆顶元素的操作:

    小根堆删除元素的代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void pop(void) {
    swap(heap[1], heap[len]);
    len--;
    down(1);
    }

    void down(void) {
    while(k * 2 <= len) {
    int j = k * 2;
    if(k*2+1 < len && heap[j+1] < heap[j]) j++;
    if(heap[k] <= heap[j]) break;
    swap(heap[k], heap[j]);
    k = j;
    }
    }
  • 堆中任意位置的删除
    删除堆中的任意一个元素时,我们可以发现这个时候这个元素下的左子树堆和右子树堆也满足堆结构,但是我们不可以像删除堆顶节点一样,和数组尾部元素互换,然后尝试下移,原因如下:

    此时无需向下调整,因为 $5<8$ 且 $5<9$,依旧满足小根堆的性质,但是其父节点 $6>5$,破坏了小根堆的性质,因此此时需要上移。
    所以我们删除堆中的任意一个元素,跟数组尾元素互换时,不仅要考虑下移,还有可能会上移。小根堆中删除一个位于数组位置 pos 的元素的代码如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void deleteElem(int pos) {
    if (pos == len) {
    heap[len] = 0;
    len--;
    return;
    }
    int x = heap[pos], y = heap[len];
    swap(heap[pos], heap[len]);
    len--;
    if (y < x) {
    // 堆尾的数比原数大, 尝试上移
    up(pos);
    } else {
    // 堆尾的数比原数小, 尝试下移
    down(pos);
    }
    }

STL 中的 priority_queue(优先队列)

STL 库中的 priority_queue 是一个很类似于堆的结构,它包含如下操作:

  • empty - 判断是否为空
  • size - 返回队列内元素个数
  • top - 访问队首元素
  • push - 往队列中插入一个元素
  • pop - 弹出队首元素

这里的 priority_queue 相当于堆,队首元素相当于堆顶元素。
我们可以使用如下语句创建一个小根堆:

1
priority_queue<int, vector<int>, greater<int>> q;

这段C++语句创建了一个优先队列 q,其中元素类型为 int,底层容器使用 vector<int>,并且使用 greater<int> 作为比较器。在优先队列中,当元素被插入队列时,会根据比较器的规则进行排序,从而实现堆的性质。

在这段语句中,greater<int> 是一个函数对象,代表使用“大于”运算符进行比较。因此,当要创建一个小根堆时,即希望队列中的元素按照从小到大的顺序排列,可以利用 greater 作为比较器,这样队列中的最小元素将位于队首。
同样的,我们可以使用如下语句创建一个大根堆:

1
2
3
4
// 写法 1:
priority_queue<int> q;
// 写法 2:
priority_queue<int, vector<int>, less<int>> q;

当使用 priority_queue<int, vector<int>, greater<int>> q; 创建一个小根堆后,可以按以下方式操作这个小根堆:

  • 插入元素:使用 push() 方法将元素插入小根堆。
    1
    2
    3
    q.push(5); // 插入元素5
    q.push(3); // 插入元素3
    q.push(7); // 插入元素7
  • 获取堆顶元素:使用 top() 方法获取小根堆的头部元素。
    1
    2
    int topElement = q.top(); // 获取小根堆的头部元素
    cout << "Top element of the min heap: " << topElement << endl;
  • 删除堆顶元素:使用 pop() 方法删除小根堆顶部的元素。
    1
    q.pop(); // 删除小根堆的头部元素
  • 查看堆是否为空:使用 empty() 方法检查小根堆是否为空。
    1
    2
    3
    4
    5
    if (q.empty()) {
    cout << "Min heap is empty" << endl;
    } else {
    cout << "Min heap is not empty" << endl;
    }

Hash

哈希(Hash)

[TOC]

哈希的基本概念

  • 哈希(Hash)在我的理解中是一种映射关系,例如,将学生映射到学号上、将口红的颜色映射到一个色号上。
  • 哈希函数(Hash Function)就是将一种你想要查询的关键字,比如说姓名、手机号码、数字或者字符串等,映射成便于查找的东西(一般来说是一个数字)的函数。
  • 一般而言,一个好的哈希函数可以帮我们将我们想要查找的东西,从一个较大集合映射到一个较小集合,然后我们可以将这个较小集合中的信息存储下来,例如存入一个数组,这个用于存储较小集合的数组就称之为哈希表
    • 一张格式如下的表:
      学号 姓名
      0001 张三
      0002 李四
      0003 王五
      0004 赵六
    • 这张表就可以理解为一个姓名和学号的哈希表,我们通过学号就可以获得学号对应的人的姓名,即:学号[0001] -> "张三",反映到代码中,可以理解为一个一维数组通过下标直接访问。
  • 而在一些加密工作中,可能需要将要简单的组合复杂化,比如密码组合,这时会有一种类似反向哈希(加密)的过程。
  • 比较常见的哈希函数的例子:
    $$H(x) = x ; mod ; 11$$
  • 这个函数可以让我们将任意的整数映射到 0 ~ 10 的范围中

哈希的基本操作

  • 定义哈希函数
    1
    2
    3
    4
    5
    6
    7
    const int modnum = 11;
    int hashTable[modnum];

    // 定义哈希函数
    int hash(int x) {
    return x % modnum;
    }
  • 在哈希表中插入元素
    1
    2
    3
    4
    5
    // 在哈希表中插入元素
    void insert(int x) {
    int addr = hash(x);
    hashTable[addr] = x;
    }
  • 在哈希表中查找元素
    1
    2
    3
    4
    5
    // 在哈希表中查找元素
    bool isExist(int x) {
    int addr = hash(x);
    return hashTable[addr] == x;
    }

哈希表中解决冲突的方式

不同关键字通过相同哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞,或者称为哈希冲突。
哈希表在存放数据时有可能出现冲突的情况,以上文中的哈希函数为例我们分别向其中插入元素,如下:

因为希望哈希表底层数组的容量小于实际要存储的关键字的数量,这就会导致一个问题:冲突的发生是必然的,我们能做的是尽量的降低冲突率

冲突的解决方式一般有以下两种:

方式 1:顺延

一种很好想到的解决方式是将哈希表中插入时产生冲突的元素向后顺延,直到找到一个空位置再进行插入。这种方式称为顺延,也有说法称之为线性探测

此时插入和查找的代码也要发生相应的改变,插入时需要我们需要找到一个空位置来执行插入操作;相对应的查找方式也要做出改变,当我们查询一个数时,也要查询哈希函数对应的位置,并依次比较连续的非空的哈希表中的值:

  • 插入操作
    1
    2
    3
    4
    5
    6
    7
    void insert(int x) {
    int addr = hash(x);
    while(hashTable[addr] NOT NULL) { // 当哈希表的插入位置不为空
    addr = (addr + 1) % modnum;
    }
    hashTable[addr] = x;
    }
  • 查找操作
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void isExist(int x) {
    int addr = hash(x);
    while(hashTable[addr] NOT NULL) { // 当哈希表的查询位置不为空(查询一段连续的哈希表)
    if(hashTable[addr] == x) { // 如果查询到指定元素, 返回 true
    return true;
    }
    addr = (addr + 1) % modnum;
    }
    return false;
    }
    可以定义多种解决冲突的顺延函数,即addr = (addr + 1) % modnum,实际使用中可以是每次$+k$,或者$+1^2$,$+2^2$,$+3^2$,…等。

但是这种顺延方式会存在一定的问题:插入时可能会出现多次冲突,当哈希表即将满的时候,插入操作的冲突可能会出现的更多,此时插入和查询操作都会变成一个非常耗时的操作。

方式 2:哈希链表

我们可以通过链表的方式,来实现在一个位置放置多个元素的操作。在 C++ 的 STL 库中,我们可以使用 STL 库中提供的 vector 来简单的替代链表。
通过这种方式,每次查找元素时,先找到对应的链表头,然后遍历这个位置的整张链表即可。

此时的哈希表的定义、插入操作和查询操作要发生相应的变化:

  • 定义哈希函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #include <iostream>
    #include <vector>

    const int modnum = 11;
    vector<int> hashTable[modnum];

    // 定义哈希函数
    int hash(int x) {
    return x % modnum;
    }
  • 插入操作

    1
    2
    3
    4
    void insert(int x) {
    int addr = hash(x);
    hashTable[addr].push_back(x);
    }
  • 查询操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void isExist(int x) {
    int addr = hash(x);
    int tableSize = hashTable[addr].size();
    // 这里不使用 for(int i = 0; i < hashTable[addr].size(); i++) 的写法, 而是首先计算出 hashTable[addr].size()
    // 因为 vector 的 size() 是一个比较耗时的操作, 他是通过将 vector 按照一个一个数出来的方式来进行计数的
    // 在数据量小的时候可能并不明显, 当数据量大的时候可能就会出现较为严重的耗时问题
    for(int i = 0; i < tableSize; i++) {
    if(hashTable[addr][i] == x) {
    return true;
    }
    }
    return false;
    }

    但是这种方式还是不能彻底解决我们的问题。对于插入操作来说,时间复杂度可以看作是$O(1)$,对于查询操作来说,时间复杂度和其冲突次数相关联。

哈希函数的设计

面对上面的问题,设计好哈希函数才是解决问题的关键。哈希函数在设计的时候,一般要注意几个原则:

  • 设计哈希函数时,我们需要尽可能让查询的值均匀地存储在哈希表中,或者说尽量分散再哈希表中。
  • 在手搓哈希函数时,我们会要求 $H(x) = x ; mod; p$,其中的 $p$ 为素数
  • 哈希函数中的对 $p$ 取摸的操作,会使得哈希值落在 $0 <= value <= p-1$ 的范围内,这个哈希表的长度 $p$,一般被称为哈希表的容量(Capacity)
  • 插入哈希表的元素总数除以哈希表的容量得到的数,称为负载因子,这里可以用 $\alpha$ 表示,即:
    $$\alpha = ElumNum \div p$$
  • 当负载因子$\alpha$达到一定程度时(一般认为是$0.7\sim0.8$),则说明再对哈希表继续进行操作,就会面临大量冲突的情况,这时就要考虑增大哈希表的容量以避免出现更多的冲突。
  • 哈希函数的冲突率和负载因子的关系一般如下:

字符串哈希

字符串哈希是学习或者工作中经常遇到的一种操作,常用于比较两组字符串的内容等操作。通过比较两个字符串的哈希值就可以完成字符串的比较。当然这个操作也可以用于数组的哈希,因为字符串本质就是一个字符数组。
$$s = s_1s_2s_3 \dots s_n\qquad s_i \in a, b \dots z$$

一个字符串 $s$ 由 $n$ 个字符组成,每个字符 $s_i$ 属于 $a \sim z$。
其哈希函数为:
$$\begin{aligned}H(S)
&=(\sum_{i=1}^{n} c_i × base^{n-i});mod ;p\
&=(c_1 × base ^ {n-1} + c_2 × base ^ {n-2} + \dots + c_{n-1} × base ^ {1}) ; mod ; p\
&=base^{n-(n-1)}(base\dots(base(base × c_1 + c_2)));mod ;p\
&=base^{1}(base\dots(base(base × c_1 + c_2)+c_3)+\dots + c_n)\end{aligned};mod ;p$$

其中 $c_i$ 是一个和 $s_i$ 有关的数字,我们可以将字符映射到数字,例如:$a → 1$、$b → 2$ 等。这里不将 a 映射为 0,因为如果将 a 映射为 0,字符串 aab 的哈希值是相等的。
$base$ 是一个可以自己指定的数字,其值一般是大于字符集中的字符数量($c_i$的最大值)的素数,这里可以取 31,常见的选择是 9999971
$p$ 是一个素数,常见的选择是 101137

用代码实现为:

1
2
3
4
5
6
7
8
int hash(char s[], int n) {
int res = 0;
for(int i = 0; i < n; i++) {
// 为什么是 res * base, 见上文的描述的公式推导
res = (res * base + (s[i] - 'a' + 1)) % p;
}
return res;
}

当 $base$ 为 31,$p$ 为 101 时。
当 $s$ 为 $a$ 时,hash(char s[], int n) 的值为 1。
过程可以描述如下:

1
2
[1] res = (0 * base + ('a' - 'a' + 1)) % p
>>> res = 1

当 $s$ 为 $ab$ 时,hash(char s[], int n) 的值为 1。
过程可以描述如下:

1
2
3
4
[1] res = (0 * base + ('a' - 'a' + 1)) % p
>>> res = 1
[2] res = (1 * base + ('b' - 'a' + 1)) % p
>>> res = 33

当我们定义好一个良好的哈希函数之后,因为哈希函数的值相等的概率比较小,当两个字符串的哈希值相同的时候,我们可以认为两个字符串也相同,从而避免使用按位比较,节约时间。

$base$ 为什么一般是一个大于字符集中的字符数量($c_i$的最大值)的素数呢?
当 $base$ 值过小时,此处假定为 $11$,会出现有可能两个字符运算完后还没有超过字母表的范围。如:字母表的范围为 $1 \sim 26$,字符串 ba 运算完成后的结果为 $23$,两个字符串的运算结果小于 $26$,字符串w运算完成后的结果为 $23$,可以发现 baw 出现了冲突。

我们字符串的定义方式有一种好处,可以使得我们借助类似前缀和的思想,快速得到任意一段字符串 $s$ 的字串的哈希值。

  • 我们可以使用一个数组 $a$ 来记录我们计算 hash(s) 的中间过程,即:
    1
    2
    3
    4
    a[1] = hash(c1)
    a[2] = hash(c1c2)
    ...
    a[i] = hash(c1c2...ci)
    那么字符串 $s$ 的任意子串 $s_{l, r} = s_ls_{l+1}\dots s_r$ 的哈希值为:
    $$hash(s_{l, r}) = (a[r] - a[l-1] × base^{r - l + 1});mod;p$$

双哈希

冲突往往是不可避免的,纵使我们的哈希函数再好,也有可能会出现冲突的情况,那么我们如何尽可能避免这个问题呢?这时候,我们可以使用双哈希的方法来避免冲突。
在上文字符串哈希中,我们的字符串哈希函数为:

$$H(S) = (\sum_{i=1}^{n} c_i × base^{n-i});mod ;p$$

那么如何实现双哈希呢?我们可以选取两组 $base$ 和 $p$,然后使用这分别使用这两组 $base$ 和 $p$,分别来求取哈希值。如果这两组参数得到的哈希值都相同,我们则认为两个字符串相等。在竞赛中,最好书写双哈希,甚至三哈希,因为这样出错误的概率会呈指数级的降低。

STL中的哈希 unordered_map

在 C++ 的STL库中,有一个非常好用的数据结构 unordered_map,可以帮助我们实现大多数哈希表的操作。

1
unordered_map<K, V> hash_table;

其中 K 为我们想要存储的关键字信息,V 表示与他关联的一些信息。例如:

1
unordered_map<string, int> hash_table;

这个表会以string作为Kint作为V进行存储,基于此我们可以很方便的实现一些功能。例如我们现在要保存一个班级上学生的年龄信息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;

int query(string name) {
if(hash_table.find(name) == hash_table.end()) {
cout << "Cannot Find..." << endl;
}
return hash_table[name];
}

int main(void) {
unordered_map<string, int> hash_table;
hash_table["zhangsan"] = 2000;
hash_table["lisi"] = 2001;
query("zhangsan");

return 0;
}

栈(Stack)

栈(Stack)

栈的基本概念

  • 栈是一种 先进后出(First in Last Out, FILO) 的数据结构,其类似于我们生活中的衣娄,衣服只能从最顶部放入,也只能从最顶部拿出,要想拿出中间的某件衣服,就需要将顶部的衣服全部拿出,再进行后续的操作。

  • 衣娄对应到栈上,就是以下的概念:

    • 栈(Stack) 是一种类似于衣娄的数据结构,我们可以向其内部存入或者取出数据
    • 栈按照 先进后出 的原则存储数据,每次新进入的数据都会被放在最上面,越先进入的越靠下,越后进入的数据越靠上。
    • 我们只能对最上面的数据进行操作
    • 栈的两大元素:栈的大小和栈顶指针Top(该指针指向栈最顶部的位置)

栈的基本操作

  • 新建栈(题目简单时可以用数组模拟栈)
  • 插入数据
  • 删除栈顶数据
  • 查询栈顶数据
  • 清空栈

复习数据结构/算法清单

复习数据结构清单

有日期则表示在该日期已经复习完毕,或者表示复习后的最新一次更新

数据结构 链接 备用链接(Backup Link) 日期
栈(Stack) - - -
队列(Queue) - - -
链表(Link List) - - -
二叉树(Binary Tree) https://hello-nilera.com/2024/05/07/Tree/ https://blog.csdn.net/NilEra/article/details/138624929?spm=1001.2014.3001.5501 2024.05.09
哈希(Hash) - - -

算法复习清单

算法 链接 备用链接(Backup Link) 日期